Порубані пари

Для масиву $A$ розміру $m$ ми кажемо, що пара $(i,j)$ є $\mathbf{порубаною}$ тоді й лише тоді, коли:

• 1 \le i < j \le m

• \min(A_i,A_j) > 0

• A_i > A_j

Вам задано масив $a$ розміру $n$.

Для цілого числа $id$ (1 \le id \le n) ми будуємо масив b_{id}, виконуючи такий алгоритм:

1. Ініціалізуйте масив $c$ розміру $n$, у якому всі елементи дорівнюють $0$.

2. Зробіть c_{id} рівним a_1 (тобто покладіть c_{id} = a_1).

3. Ініціалізуйте i=2.

4. Виберіть максимальний індекс 1 \le j \le n, для якого c_j = 0, такий, що якщо покласти c_j = a_i, то масив $c$ матиме мінімальну кількість $\mathbf{порубаних}$ пар (зверніть увагу, що потрібно мінімізувати кількість $\mathbf{порубаних}$ пар у поточному масиві $c$ після присвоєння c_j = a_i, $\mathbf{АНЕ}$ у фінальному масиві $c$ після завершення алгоритму).

5. Зробіть c_j рівним a_i (тобто покладіть c_j = a_i).

6. Якщо i=n, завершіть алгоритм, інакше збільште $i$ на $1$ і поверніться до кроку $4$.

b_{id} дорівнює отриманому масиву $c$.

Для кожного 1 \le id \le n обчисліть кількість $\mathbf{порубаних}$ пар у масиві b_{id}.