# 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 · 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$ ($1 \le n \le 100000$) as input. Here, $n$ denotes the total number of elements in the array. Then you will take $n$ numbers as input to your array ($1 \le array_i \le 10^9$). Next, you will take an integer $m$ ($1 \le m \le 100000$) as input. Here, $m$ denotes the total number of queries. Finally, for each query, you will take the index $k$ ($1 \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[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.

### Statistics

69% Solution Ratio

m1n2o3Earliest, May '18

Shuvo_MalakarFastest, 0.0s

dipta007Lightest, 2.0 MB

S_SubrataShortest, 950B