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.


Submit

Login to submit.

Statistics

72% Solution Ratio
m1n2o3Earliest, May '18
MehedyhassanFastest, 0.0s
dipta007Lightest, 2.0 MB
S_SubrataShortest, 950B
Toph uses cookies. By continuing you agree to our Cookie Policy.