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.
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.
1 <= array[i] <= 109
(First index of the array is considered as 1 instead of 0)
For each query, you have to print the minimum number of swaps.
3 3 2 1 1 2
7 3 1 2 5 6 7 4 1 4
In the second sample test , you should swap (A, A).
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.