Finally, COVID-19 has been eradicated! To celebrate, you and your neighbours decide to meet up to have a massive party. You and your neighbours live along a street with ~N~ houses numbered ~1~ to ~N~. Each house is at a height of ~a_i~. The travel cost from house ~x~ to house ~y~ is defined as: ~\sum_{k=\min(x,y)}^{\max(x,y)-1}|a_{k+1}-a_k|~ or ~0~ if ~x = y~.

To have a party at house ~x~, everyone must come to house ~x~. The total cost of having the party at house ~x~ is the sum of the travel costs of each individual house travelling to house ~x~. However, not everyone on your street is willing to host such a massive party. More specifically, out of you and your neighbours, only ~Q~ people are willing to host it. To help determine the best house to have the party, you have compiled all the house numbers into a list ~h~ that would be willing to host a party. For each house in ~h~, print out the cost of having a party at ~h_i~.

Input Specification

The first line will contain the positive integer ~N~, the number of houses on your street.

The second line will contain ~N~ space-separated positive integers, ~a_i~, the height of the ~i^\text{th}~ house.

The third line will contain the positive integer ~Q~, the number of people willing to host the party.

The next ~Q~ lines will contain a positive integer ~h_i~.

Output Specification

For each house number ~h_i~, print out the corresponding cost of hosting a party at ~h_i~.

Constraints

For all subtasks:

~3 \le N \le 10^6~

~0 \le a_i \le 10^6~

~1 \le Q \le 10^6~

~1 \le h_i \le N~

Subtask 1 [10%]

~3 \le N \le 400~

~1 \le Q \le 400~

Subtask 2 [20%]

~3 \le N \le 4 \times 10^3~

~1 \le Q \le 4 \times 10^3~

Subtask 3 [70%]

No additional constraints.

Sample Input 1

4
1 2 5 1
2
2
4

Sample Output 1

11
19

Sample Input 2

8
1 3 2 5 999 0 6 6
5
6
5
4
3
2

Sample Output 2

8996
6998
6998
7004
7008