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