该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

信息学冬令营以传统舞蹈结束。共有$n$名学生参与，每人都有一个唯一的编号，范围在$1$到$n$之间。

首先，指挥$Krešo$让学生们围成一个圈，每名学生与另外两名学生手拉手。

$Alenka$想知道是否可以通过恰好让一对相邻的学生松开手，使得新形成的学生序列按编号排序。例如，如果顺序是$3$ $4$ $1$ $2$，那么可以在编号为$4$和$1$的学生之间断开圆圈；但如果顺序是$2$ $1$ $4$ $3$，则无法以这种方式断开圆圈。

在夜间，$Krešo$将给出$q$条指令。每条指令中，他会命令两名学生交换位置。每次交换后，你需要帮助$Alenka$回答她的问题。

输入格式

第一行包含两个整数$n$和$q$（$1 \leq n,q \leq 300000$），分别表示学生数量和交换次数。

第二行包含$n$个整数$a_{i}$（$1 \leq a_{i} \leq n$），描述初始时圆圈中学生的编号。

接下来的$q$行中，每行包含两个整数$x_{i}$和$y_{i}$（$1 \leq x_{i},y_{i} \leq n$，$x_{i} \neq y_{i}$），表示$Krešo$的第$i$条指令，即编号为$x_{i}$和$y_{i}$的学生交换位置。

输出格式

对每一次交换（共$q$次），输出一行答案：

• 若在该交换之后存在一种断开方式满足条件，输出$DA$；
• 否则输出$NE$。

数据范围

对于$100\%$的数据，满足$1 \leq n,q \leq 3 \times 10^{5}$，$1 \leq a_{i} \leq n$，$1 \leq x_{i},y_{i} \leq n$，$x_{i} \neq y_{i}$。

样例数据

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

Limitation

初始状态的学生、第一次交换后的学生以及第二次交换后的学生

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

NE
NE
DA
NE
DA