Problem Description

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.

Input Format

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 Format

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.

5 2
2 3 4 5 1
1 3
3 1

NE
DA

4 2
2 3 1 4
4 2
3 4

NE
DA

6 5
2 1 5 6 3 4
3 1
3 4
3 2
4 5
5 4

NE
NE
DA
NE
DA

Hint

[Sample Explanation #2]

[Constraints]

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