Interval Groups

The integers from 1 through N are written on a board from left to right in some order.

A group is valid when the set of numbers inside it forms one consecutive integer interval. For instance, [2], [4 5], and [3 5 6 4] are valid groups because their sets are {2}, {4, 5}, and {3, 4, 5, 6}. The groups [5 7 2] and [2 4 5] are not valid because their sets are not consecutive intervals.

Initially, each number is a group by itself. One operation may concatenate two currently adjacent groups, but only if the newly formed group is also valid.

Determine whether N-1 operations can make all numbers belong to one group. If it is possible, output any one valid sequence of operations.

The first line contains an integer N. (1 ≤ N ≤ 500,000)

The second line contains N positive integers separated by single spaces, in the order written on the board. They are the integers from 1 through N, each appearing exactly once.

If the requested sequence exists, print DA on the first line; otherwise print NE.

If you print NE, do not print anything else.

If you print DA, then print N-1 more lines describing the operations in order. For the i-th operation, print two integers: the smallest and largest number in the group created by that operation.