P16363 [OOI 2026] Participants entry

At the open programming olympiad for school students, there are $n$ participants numbered from $1$ to $n$. Participant number $i$ is wearing a t-shirt of color $a_i$. The organizers of the competition plan to invite participants to the competition hall in turn. To make this process visually pleasing, they want to avoid situations where two consecutive participants enter wearing t-shirts of the same color. To achieve this, participants will be invited according to the following algorithm: - The first participant to enter the competition hall is participant number $1$. - invited must have a t-shirt color that differs from the color of the last participant who entered. If there are several such participants, the one with the smallest number is chosen. - Finally, if all remaining participants have the same t-shirt color as the last participant who entered, all remaining participants are invited in increasing order of their numbers. On the night before the olympiad, the organizers prepared a plan for the participants entry, but just before the opening, they noticed that participants with neighboring numbers sometimes swap t-shirts. Of course, this led to the previous plan no longer complying with the rules, and the organizers needed to develop a new one. You are required to respond to two types of queries: - Two participants with numbers $x_i$ and $(x_i + 1)$ swap t-shirts. - Find out the order in which participant number $y_i$ will enter if participants start entering according to the algorithm described above, starting from the first one, taking into account all previous t-shirt swaps.

The first line contains two integers $n$ and $q$ ($1 \le n \le 500\,000$, $1 \le q \le 500\,000$) --- the number of participants in the competition and the number of queries. The second line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le n$) --- the initial colors of the participants' t-shirts in the order of their numbering. The following $q$ lines describe the queries. In the $i$-th line, there is an integer $t_i$ ($1 \le t_i \le 2$) --- the type of the $i$-th query. - If $t_i = 1$, then the next line contains an integer $x_i$ ($1 \le x_i < n$). In this case, in the $i$-th query, participants with numbers $x_i$ and $(x_i + 1)$ swap t-shirts. - If $t_i = 2$, then the next line contains an integer $y_i$ ($1 \le y_i \le n$). In this case, in the $i$-th query, you need to find out the order in which participant number $y_i$ will enter if participants start entering according to the algorithm described above, starting from the first one, taking into account all previous t-shirt swaps.

For each query of the second type, you should output a single integer on a separate line --- the answer to the query. It is guaranteed that there is at least one query of the second type.

### Note In the first example for the problem, in the initial configuration, participants enter the competition hall in the order: $$1, \quad 2, \quad 4, \quad 3, \quad 5, \quad 6, \quad 8, \quad 7, \quad 9, \quad 10$$ That is, participant number $2$ enters second, participant number $3$ enters fourth, participant number $4$ enters third, and participant number $10$ enters tenth. After participants with numbers $1$ and $2$ swap t-shirts, the t-shirt colors of the participants are as follows: $$1, \quad 3, \quad 1, \quad 2, \quad 2, \quad 1, \quad 1, \quad 2, \quad 2, \quad 2$$ Therefore, after this change, participants will enter the competition hall in the order: $$1, \quad 2, \quad 3, \quad 4, \quad 6, \quad 5, \quad 7, \quad 8, \quad 9, \quad 10$$ That is, participant number $2$ will enter second, participant number $3$ will enter third, participant number $4$ will enter fourth, participant number $5$ will enter sixth, and participant number $10$ will enter tenth. In the second example for the problem, in the initial configuration, participants enter the competition hall in the order: $$1, \quad 2, \quad 5, \quad 3, \quad 6, \quad 4, \quad 7, \quad 8, \quad 9, \quad 10$$ That is, participant number $1$ enters first. After participants with numbers $1$ and $2$ swap t-shirts, the t-shirt colors of the participants are as follows: $$2, \quad 1, \quad 2, \quad 2, \quad 3, \quad 4, \quad 5, \quad 6, \quad 7, \quad 8$$ Therefore, after this change, participants will enter in the order: $$1, \quad 2, \quad 3, \quad 5, \quad 4, \quad 6, \quad 7, \quad 8, \quad 9, \quad 10$$ That is, participant number $2$ enters second. After participants with numbers $2$ and $3$ swap t-shirts, the t-shirt colors of the participants are as follows: $$2, \quad 2, \quad 1, \quad 2, \quad 3, \quad 4, \quad 5, \quad 6, \quad 7, \quad 8$$ Therefore, after this change, participants will enter the competition hall in the order: $$1, \quad 3, \quad 2, \quad 5, \quad 4, \quad 6, \quad 7, \quad 8, \quad 9, \quad 10$$ That is, participant number $3$ enters second. After participants with numbers $3$ and $4$ swap t-shirts, the t-shirt colors of the participants are as follows: $$2, \quad 2, \quad 2, \quad 1, \quad 3, \quad 4, \quad 5, \quad 6, \quad 7, \quad 8$$ Therefore, after this change, participants will enter in the order: $$1, \quad 4, \quad 2, \quad 5, \quad 3, \quad 6, \quad 7, \quad 8, \quad 9, \quad 10$$ That is, participant number $4$ enters second. After participants with numbers $4$ and $5$ swap t-shirts, the t-shirt colors of the participants are as follows: $$2, \quad 2, \quad 2, \quad 3, \quad 1, \quad 4, \quad 5, \quad 6, \quad 7, \quad 8$$ Therefore, after this change, participants will enter in the order: $$1, \quad 4, \quad 2, \quad 5, \quad 3, \quad 6, \quad 7, \quad 8, \quad 9, \quad 10$$ That is, participant number $3$ enters fifth, and participant number $5$ enters fourth. ### Scoring The tests for this problem consist of 12 groups. Points for each group are awarded only if all tests in the group and all tests in some of the previous groups are passed. Note that passing the tests from the statement is not required for some groups. $\textbf{Offline verification}$ means that the results of testing your solution on this group will only be available after the competition ends. The final score for each group is equal to the maximum score obtained for this group of tests across all submitted solutions. | Group | Points | Additional constraints | Required groups | Comment | |:-----:|:------:|:----------------------:|:---------------:|:-------:| | | | $n, q$ | | | | 0 | 0 | -- | -- | Tests from the statement. | | 1 | 7 | $n, q \le 500$ | 0 | | | 2 | 9 | $n, q \le 5\,000$ | 0, 1 | | | 3 | 5 | $n, q \le 10\,000$ | 0--2 | | | 4 | 10 | $n, q \le 100\,000$ | 0--3 | | | 5 | 8 | $n, q \le 200\,000$ | 0--4 | | | 6 | 7 | $n, q \le 300\,000$ | 0--5 | | | 7 | 9 | -- | -- | $1 \le a_i \le 2$ | | 8 | 9 | -- | 7 | $1 \le a_i \le 5$ | | 9 | 11 | -- | -- | For any $i \neq j$: $a_i = 1$ or $a_i \neq a_j$
If $t_i = 2$, then $y_i = \left\lceil \frac{9n}{10}\right\rceil$ | | 10 | 8 | -- | 9 | For any $i \neq j$: $a_i = 1$ or $a_i \neq a_j$ | | 11 | 9 | -- | 9 | If $t_i = 2$, then $y_i = \left\lceil \frac{9n}{10}\right\rceil$ | | 12 | 8 | -- | 0--11 | **Offline testing.** |