Minimizing Circular Difference in a Permutation

You are given a sequence \(\{a_n\}\) containing one or more integers. You have to process m operations on the sequence. Each operation is one of the following two types:

• 1 x: Delete one occurrence of an integer \(x\) from the sequence. If \(x\) does not exist in the sequence, output \(-1\) and skip the current operation.
• 2 x: Insert an integer \(x\) into the sequence.

After each non-skipped operation, you need to output a permutation \(p\) of the current sequence \(a\) such that the following quantity is minimized:

[ \sum_{i=1}^{n} \lvert p_{i+1} - p_i \rvert \quad \text{with} \quad p_{n+1} = p_1, ]

A permutation \(p\) of \(a\) is any rearrangement of \(a\) (i.e. for every integer \(x\), the number of occurrences of \(x\) in \(p\) equals that in \(a\)). It can be shown that arranging the sequence in non-decreasing order yields the minimal sum value of \(2\times(\max(a)-\min(a))\).

Note: It is guaranteed that at any point the sequence will contain at least one element.

inputFormat

The first line contains an integer \(n\) \( (n \ge 1)\), the size of the initial sequence.

The second line contains \(n\) space-separated integers representing the initial sequence.

The third line contains an integer \(m\), the number of operations.

Each of the next \(m\) lines contains an operation formatted as either 1 x or 2 x, where \(x\) is an integer.

outputFormat

For each operation:

• If the operation is of type 1 x and \(x\) is not present in the sequence, output a single line with \(-1\).
• Otherwise, update the sequence accordingly and output a single line containing a permutation \(p\) (in non-decreasing order) of the current sequence. The numbers in \(p\) should be separated by a single space.

sample

3
1 3 2
3
1 3
2 4
1 5

1 2
1 2 4
-1