A loading dock scans pallets one by one as they roll off an incoming truck. Each pallet carries a unique serial number, and the scanner has already sorted these numbers into strictly increasing order before handing them to you. The dock crew groups pallets into storage blocks: a block is a maximal run of scanned serial numbers in which each number is exactly one greater than the number before it (that is, the numbers in the run are consecutive integers with no gaps). Given the sorted serial numbers, report every storage block, in the order the numbers appear, as its starting and ending serial number.

Input format

• Line 1: a single integer n — the number of pallets scanned.
• Line 2: n space-separated integers id[0], id[1], ..., id[n-1], given in strictly increasing order — the serial numbers.

Output format

Print one line per storage block, in increasing order of starting number, as two space-separated integers start end — the smallest and largest serial number in that block. A block containing a single pallet has start == end.

Constraints

• 1 <= n <= 100000
• -10^9 <= id[i] <= 10^9
• id is strictly increasing (id[i] < id[i+1] for all valid i), so all values are distinct.

6
1 2 3 6 7 9

1 3
6 7
9 9

1
5

5 5