P9757 [COCI 2022/2023 #3] Dirigent

The informatics winter camp ends with a traditional dance. There are $n$ students participating. Each of them has a distinct ID from $1$ to $n$. At the beginning, the conductor Kreso asks the students to form a circle, so that each student is holding hands with two other students. Alenka wants to know whether it is possible, by separating the hands of exactly one pair of adjacent students, to obtain a sequence of students that is sorted by ID. For example, if their order is `3 4 1 2`, then the circle can be cut between students `4` and `1`; but if the order is `2 1 4 3`, then there is no valid way. That evening, Kreso is going to issue $q$ commands. In each command, he asks two students to swap positions. After each swap, you need to help Alenka answer her question.

The first line contains two integers $n, q$, representing the number of students and the number of swaps. The second line contains $n$ integers $a_i$, where $a_i$ is the student ID at position $i$. In the next $q$ lines, each line contains two integers $x_i, y_i$, describing Kreso's $i$-th command: the student with ID $x_i$ and the student with ID $y_i$ swap positions.

Output $q$ lines. On the $i$-th line, output the answer to Alenka's question after the $i$-th swap. If the answer is yes, output `DA`; otherwise output `NE`.

**[Sample Explanation #2]**  **[Constraints]** | Subtask | Points | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n, q \leq 500$ | | $2$ | $20$ | $n, q \leq 5000$ | | $3$ | $35$ | No special properties. | For $100\%$ of the testdata, $1 \leq n, q \leq 3 \times 10^5$, $1 \leq a_i \leq n$, $1 \leq x_i, y_i \leq n$, and $x_i \neq y_i$. The full score for this problem is $70$ points. Translated by ChatGPT 5