Empty Sequence Deletion

We are given a sequence \(a_1,a_2,\dots,a_n\) of integers and a deletion operation defined as follows: Let the current length of the sequence be \(k\); then delete all elements equal to \(k\). A sequence is called emptyable if after finitely many such deletion operations it becomes empty.

You are also given \(m\) modification queries on the sequence. Each modification is one of the following types:

• 1 pos x: Change the element at position pos (1-indexed) to x.
• 2: Increase every element in the sequence by 1.
• 3: Decrease every element in the sequence by 1.

After each modification query, you are allowed to further modify some elements (by changing their value arbitrarily) so that the sequence becomes emptyable (that is, a sequence of deletion operations eventually deletes the entire sequence). Your task is to output, after each query, the minimum number of extra individual modifications needed to make the current sequence emptyable.

Note on deletion process: Suppose the sequence has current length \(k\) and let \(f(k)\) be the number of elements equal to \(k\). A valid deletion operation can be performed only if \(f(k) \ge 1\) and it then removes exactly \(f(k)\) elements so that the new length becomes \(k-f(k)\). Hence, a sequence is emptyable if there exists a chain of positive integers \(r_1,r_2,\dots,r_t\) with \(r_i \le k_{i-1}\) and \(\sum_{i=1}^{t}r_i=n\) (where \(k_0=n\) and \(k_i=k_{i-1}-r_i\)) such that for each intermediate step the frequency of the number equal to the current length is at least the corresponding chosen \(r_i\>.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 1000\)).

The second line contains \(n\) integers representing the initial sequence \(a_1,a_2,\dots,a_n\).

Each of the next \(m\) lines describes a modification query in one of the following formats:

• 1 pos x: set \(a_{pos}\) to \(x\) (1-indexed).
• 2: add 1 to every element of the sequence.
• 3: subtract 1 from every element of the sequence.

It is guaranteed that the numbers in the sequence and the values \(x\) can be any integers.

outputFormat

After each modification query, output a single line containing one integer: the minimum number of extra modifications (i.e. changes of individual elements to an arbitrary integer) required to make the current sequence emptyable.

sample

3 3
1 2 3
2
1 2 3
3

1
1
0