Interval Groups
Time limit1sMemory limit128 MB
Given a permutation of 1..N arranged on a board, decide if adjacent groups can be merged repeatedly into intervals until one group remains, and output the merge sequence if possible.
- Level
Medium7 of 10
- Topics
- Greedy, Stack, Union-find, Simulation
- Solved
- No attempts yet
Problem
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.
Input
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.
Output
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.