Chopped Pairs

For an array $A$ of size $m$, we say that a pair $(i,j)$ is $\mathbf{chopped}$ iff:

• 1 \le i < j \le m

• \min(A_i,A_j) > 0

• A_i > A_j

You're given an array $a$ of size $n$.

For an integer $id$ (1 \le id \le n), we construct the array b_{id} by performing the following algorithm:

1. Initialize an array $c$ of size $n$ where all elements are $0$.

2. Make c_{id} equal to a_1 (set c_{id} = a_1).

3. Initialize i=2.

4. Pick the maximum index 1 \le j \le n where c_j = 0, such that making c_j = a_i results in the array $c$ with the minimum number of $\mathbf{chopped}$ pairs (Note that you need to minimize the number of $\mathbf{chopped}$ pairs in the current array $c$ after setting c_j = a_i $\mathbf{NOT}$ in the final array $c$ after the algorithm ends).

5. Make c_j equal to a_i (set c_j = a_i).

6. If i=n, end the algorithm, otherwise increase $i$ by $1$ and go back to step $4$.

b_{id} is equal to the resulting array $c$.

For each 1 \le id \le n, calculate the number of $\mathbf{chopped}$ pairs in the array b_{id}.