구간 그룹

1부터 N까지의 서로 다른 자연수가 칠판에 왼쪽에서 오른쪽 순서로 적혀 있다.

어떤 그룹에 들어 있는 수들의 집합이 하나의 연속된 정수 구간이면 그 그룹을 구간 그룹이라고 한다. 예를 들어 [2], [4 5], [3 5 6 4]는 각각 들어 있는 수가 {2}, {4, 5}, {3, 4, 5, 6}이므로 구간 그룹이다. 반면 [5 7 2]와 [2 4 5]는 들어 있는 수가 연속된 구간이 아니므로 구간 그룹이 아니다.

처음에는 각 수 하나가 하나의 그룹이다. 한 번의 연산에서는 현재 서로 이웃한 두 그룹을 이어 붙일 수 있다. 단, 이어 붙인 뒤 생기는 새 그룹도 구간 그룹이어야 한다.

N-1번의 연산으로 모든 수를 하나의 그룹으로 만들 수 있는지 판정하라. 가능하다면 그런 연산 순서 하나를 출력하라.

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄에 칠판에 적힌 순서대로 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수들은 1부터 N까지의 정수이며 각각 정확히 한 번씩 등장한다.

가능하다면 첫째 줄에 DA를, 불가능하다면 NE를 출력한다.

NE를 출력하는 경우에는 더 출력하지 않는다.

DA를 출력하는 경우에는 이어지는 N-1개의 줄에 연산을 순서대로 출력한다. i번째 연산으로 새로 만든 그룹에 들어 있는 가장 작은 수와 가장 큰 수를 공백으로 구분해 출력한다.