Problem Description

The Informatics Winter Camp concludes with a traditional dance. There are $n$ students participating, each with a unique number between $1$ and $n$.

Initially, the conductor Kreso instructs the students to form a circle, ensuring that each student holds hands with two others.

Alenka wonders if it is possible to break the handhold between exactly one pair of adjacent students such that the resulting sequence of students is sorted by their numbers. For example, if their order is 3 4 1 2, the circle can be broken between students 4 and 1; but if the order is 2 1 4 3, there is no valid way to do so.

Kreso plans to issue $q$ instructions. In each instruction, he will require two students to swap places. After each swap, you need to help Alenka answer her question.

Input Format

The first line contains two integers $n$ and $q$, representing the number of students and the number of swaps, respectively.

The second line contains $n$ integers $a_i$, describing the student number at the $i$-th position.

The next $q$ lines each contain two integers $x_i$ and $y_i$, describing Kreso's $i$-th instruction, where students numbered $x_i$ and $y_i$ swap places.

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 affirmative, output DA; otherwise, output NE.

Sample Input and Output

Sample Input #1

5 2
2 3 4 5 1
1 3
3 1

Sample Output #1

NE
DA

Sample Input #2

4 2
2 3 1 4
4 2
3 4

Sample Output #2

NE
DA

Sample Input #3

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

Sample Output #3

NE
NE
DA
NE
DA

Notes

[Sample Explanation #2]

[Data Range]

For $100\%$ of the data, it is guaranteed that $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$.

This problem is worth $70$ points.

见题面 Input 部分

见题面 Output 部分