Limits 1s, 256 MB

A group of cp enthusiastic students from University of Dhaka were on a fun journey. They brought along a special array passport called AA from their university. This passport was a list of nn distinct numbers from 11 to nn.

As they explored, they discovered a bunch of mysterious boxes. Each box had a number written on it. There were qq of these boxes in total. The students knew that these numbers held the key to unlocking the secrets inside the boxes.

To open the boxes and reveal the treasures hidden inside, they had to follow a set of rules. First, they sorted their array passport carefully in ascending order. Then, they needed to reverse part of the sorted list, starting from index xx and going to the end of the list.

After each time they followed these rules, they discovered a special code or password that unlocked each of the qq mystery boxes. They calculated this password by adding up the numbers in their list, but each number had to be multiplied by its position in the list.

Formally, the password of the box written the number xx on top of it is calculated as follows:

  • Sort the array AA

  • Reverse A[xn]A[x\dots n]

  • Calculate i=1nA[i]i\sum\limits_{\substack{\text{i=1}}}^nA[i]\cdot i

Feeling very tired from their long journey, they came to you for help in figuring out how to open the boxes. They showed you their special array passport and the numbers on each of the mystery boxes. Can you give them a hand?

Input

The problem contains multiple test cases.

The first line contains the number of test cases tt (1t104)(1 \le t\le 10^4). The description of the test cases follows-

The first line of each test case contains a single integer nn (1n2105)(1 \le n \le 2\cdot10^5 )

The second line of each test case contains nn space-separated distinct integer from 11 to nn denoting the array passport AA.

The next line contains an integer qq (1q2105)(1 \le q \le 2\cdot10^5) denoting the number of boxes.

Each of the next qq lines contain an integer xx (1xn)(1\le x\le n)

It is guaranteed that the sum of nn over all test cases does not exceed 21052\cdot10^5. It is also guaranteed that the sum of qq over all test cases does not exceed 21052\cdot10^5.

Output

For each of the boxes, output the password in a new line.

Sample

InputOutput
1
7
5 4 7 3 6 1 2
5
4
3
6
7
5
130
120
139
140
136

In the sample input, the first box contains the number 44.

After sorting the array: it becomes [1,2,3,4,5,6,7][1, 2, 3, 4, 5, 6, 7]

Reversing the segment [47][4\dots 7] it becomes [1,2,3,7,6,5,4][1, 2, 3, 7, 6, 5, 4]

So, the password is 11+22+33+74+65+56+47=1301\cdot 1 + 2\cdot 2 + 3\cdot 3 + 7\cdot 4 + 6\cdot 5 + 5\cdot 6 + 4\cdot 7 = 130


Submit

Login to submit.

Statistics

85% Solution Ratio
IamHotEarliest, 5M ago
Tahmid690Fastest, 0.1s
waseemzisanLightest, 5.2 MB
waseemzisanShortest, 701B
Toph uses cookies. By continuing you agree to our Cookie Policy.