Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Left and Right

By tahmedge, CLown1331 · Limits 1s, 512 MB

You are given an array of nn distinct integers. You will take index kk as input and have to find out minimum number of swaps that you have to make so that all the numbers left to kk will be less than the value at index kk and all the numbers right to kk will be greater than the value at index kk.

Input

First you will take an integer nn (1n1000001 \le n \le 100000) as input. Here, nn denotes the total number of elements in the array. Then you will take nn numbers as input to your array (1arrayi1091 \le array_i \le 10^9). Next, you will take an integer mm (1m1000001 \le m \le 100000) as input. Here, mm denotes the total number of queries. Finally, for each query, you will take the index kk (1k1000001 \le k \le 100000; first index of the array is considered as 1 instead of 0) as input and compute the minimum number of swaps.

Output

For each query, you have to print the minimum number of swaps.

Samples

InputOutput
3
3 2 1
1
2
1
InputOutput
7
3 1 2 5 6 7 4
1
4
1

In this sample test, you should swap (A[4]A[4], A[7]A[7]).

That will give you the sequence (3,1,2,4,6,7,5)(3, 1, 2, 4, 6, 7, 5).

Now, all the values left of index 4, are smaller than the value in it and all the values in the right are larger.


Discussion

Statistics


69% Solution Ratio

m1n2o3Earliest, May '18

Shuvo_MalakarFastest, 0.0s

dipta007Lightest, 2.0 MB

S_SubrataShortest, 950B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.