Sorting Selected Suffix Elements¶
Estimated time limit: 0.5 seconds. Memory limit: 256 MB.
The deployed limit is the standard program’s largest input median in the target environment multiplied by \(2\) and rounded up to a multiple of \(0.5\) seconds. See the benchmark notes.
Story¶
A sorting station has a row of numbered crates. Each instruction sorts one crate and the smaller crates after it within their selected positions. The manager tracks the remaining inversions.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
An integer array \(a\) has length \(n\) . An inversion is a pair \((i,j)\) with \(1\le i<j\le n\) and \(a_i>a_j\) .
An operation chooses position \(k\) . Using the array at the start of the operation, form
Sort the selected values into nondecreasing order and put them back into the same positions, with smaller values at smaller indices. Other positions stay unchanged. Position \(k\) itself is included; later positions equal to \(a_k\) are excluded.
There are \(m\) operations, each specified by integer \(q\) . If \(q>0\) , use \(k=q\) ; otherwise use
where \(\mathrm{ans}\) is the previous output and the remainder lies in \(0,\ldots,n-1\) . The first operation uses the initial inversion count as \(\mathrm{ans}\) .
Input¶
The first line contains \(n,m\) . The second contains \(a_1,\ldots,a_n\) . Each of the next \(m\) lines contains one integer \(q\) .
Output¶
Print \(m+1\) lines: the initial inversion count followed by the count after every operation.
Samples¶
Sample 1¶
Input¶
3 2
2 3 1
1
1
Output¶
2
1
1
Sample 2¶
Input¶
4 2
2 2 1 0
1
1
Output¶
5
1
1
Sample 3¶
Input¶
4 3
3 -1 3 0
-4
-8
2
Output¶
3
3
3
3
Sample explanations¶
In sample one, sorting positions \(1,3\) produces \((1,3,2)\) with one inversion. Selecting position \(1\) again changes nothing. In sample two, sorting positions \(1,3,4\) gives \((0,2,1,2)\) ; the next operation changes nothing. Sample three illustrates mathematical remainders for negative instructions.
Constraints and guarantees¶
\(1\le n,m\le100000\) , \(|a_i|\le10^9\) , and \(q\in[-10^9,-1]\cup[1,n]\) . All input values are integers.
| Score | Additional constraints |
|---|---|
| 100% | None |