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 n distinct integers. You will take index k as input and have to find out minimum number of swaps that you have to make so that all the numbers left to k will be less than the value at index k and all the numbers right to k will be greater than the value at index k.

Input

First you will take an integer n as input. Here, n denotes the total number of elements in the array. Then you will take n numbers as input to your array.
Next, you will take an integer m as input. Here, m denotes the total number of queries.
Finally, for each query, you will take the index k as input and compute the minimum number of swaps.

Constraints:

1<=n<=100000,
1<=m<=100000,
1<=k<=100000,
1 <= array[i] <= 109
(First index of the array is considered as 1 instead of 0)

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

NOTE :
In the second sample test , you should swap (A[4], A[7]).
That will give you the sequence (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


67% Solution Ratio

m1n2o3Earliest, May '18

cloud007Fastest, 0.1s

dipta007Lightest, 2.0 MB

S_SubrataShortest, 950B

Submit

Login to submit

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