Problem G
Reconstructing Tape Art
Raelynn has decided the best way to learn is by copying Sheila, the world-famous tape artist. Unfortunately those pieces of art are under lock and key and Raelynn can see only pictures of these marvels. Since Raelynn is having trouble reverse engineering the artwork from the picture, she has hired you to create a set of instructions with which she can copy the art.
Since Raelynn is spoiled by the ease of IKEA catalogs she requires instructions to be given in the following format: there should only be one instruction per color of tape and instructions should be given in the order they should be executed.
Input
The input consists of a single test case. The first line of this test case contains one integer $n$ ($1 \le n \le 10^5$), where $n$ is the length of the tape art in inches. The next line contains $n$ integers $c_ i$ ($1 \le c_ i \le n$) representing the color of one inch of the plank. Planks are divided into $n$ $1$-inch sections numbered $1$ through $n$.
Output
Output any set of instructions that, when executed, will result in the tape art given by the input. The set of instructions should start with the number of instructions that follow. Each instruction must consist of three numbers: $l$ $r$ $c$ where $[l, r]$ represents the inclusive range on which the tape should be placed and $c$ represents the color of the tape piece.
Output the string “IMPOSSIBLE” if the piece of tape art cannot be reconstructed using only one piece of each color (Sheila must have broken the rules to make it or this piece is a forgery).
| Sample Input 1 | Sample Output 1 |
|---|---|
6 1 2 3 3 2 1 |
3 1 6 1 2 5 2 3 4 3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 2 1 2 |
IMPOSSIBLE |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 3 3 3 5 4 2 4 4 5 1 |
5 4 9 5 5 8 4 10 10 1 6 6 2 1 3 3 |
