Counting Swaps in Paimon's Sorting Algorithm

Paimon invented a new sorting algorithm which resembles \(\textit{bubble sort}\) with a twist. The algorithm sorts a 1-indexed sequence \(A\) of length \(n\) as follows:

// The Sorting Algorithm
SORT(A)
  for i from 1 to n
    for j from 1 to n
      if a[i] < a[j]
        Swap a[i] and a[j]

Your task is to simulate this algorithm. Given an integer sequence \(A = a_1, a_2, \ldots, a_n\), for each prefix \(A_k = a_1, a_2, \ldots, a_k\) where \(1 \le k \le n\), determine the total number of swaps performed when \(\text{SORT}(A_k)\) is executed.

inputFormat

The first line contains an integer \(n\) representing the length of the sequence.

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\).

outputFormat

Output \(n\) space-separated integers. The \(k\)-th integer should be the number of swaps performed when sorting the prefix \(A_k\) using Paimon’s algorithm.

sample

2
3 1

0 1