Problem G
Reconstructing Tape Art

Source: pixabay
Raelynn is trying to learn the newest craze in modern art: Tape Art! This wonderful new type of art is created by taking a wooden plank and pieces of tape of different colors. Each artwork is constructed by taking multiple pieces of tape and placing them on the plank. For each color that appears in the artwork, only a single piece of tape is used. Tapes can be placed on top of each other in which case the tape placed last obscures already placed pieces of tape with which it overlaps.

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.


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 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
1 2 3 3 2 1
1 6 1
2 5 2
3 4 3
Sample Input 2 Sample Output 2
1 2 1 2
Sample Input 3 Sample Output 3
3 3 3 5 4 2 4 4 5 1
4 9 5
5 8 4
10 10 1
6 6 2
1 3 3

Please log in to submit a solution to this problem

Log in