P11080 [ROI 2019] Photo (Day 1)

Translated from [ROI 2019 D1T1](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day1.pdf). Students participating in the Olympiad come from $n$ regions, and the delegation from each region consists of $m$ students. The students in each delegation wear clothes with features unique to their region; the color number of the clothes worn by the $i$-th delegation is $i$. The photographer decides to take one photo of all contestants. To organize the photo, the photographer plans to do the following: There is a row of positions on the stage where students can stand, numbered from $1$ to $m$ along the stage. The photographer plans to call, one by one, the leaders of some delegations and ask several students from that delegation to come onto the stage. The photographer specifies values $L$ and $R$, and the chosen delegation’s students come up and stand on all positions from $L$ to $R$ (including $L$ and $R$). If a position is already occupied by a student, that student is asked to leave the stage and the new student takes the position. Each delegation leader can be called by the photographer at most once.

To make the colors in the photo look more harmonious, the photographer wants there to be $m$ students in the photo, and the colors of their clothes must be arranged in the given order. Now he wants to know how to obtain the required photo. Write a program that, given the desired color order, determines the sequence of delegations the photographer should call and the positions they should occupy to produce the desired photo. If it is impossible, output `-1`.

The first line contains two integers $m$ and $n$. The second line contains $m$ integers $a_1,a_2,\dots,a_m$ ($1\le a_i\le n$), representing the desired order of clothing colors in the photo.

The first line of output should contain an integer $k$. If it is impossible to take the desired photo, this number should be $-1$. Otherwise, it should be the number of delegations the photographer needs to call in order to take the desired photo. When $k\ne-1$, the next $k$ lines should output the photographer’s requests in the order they should be made. The $i$-th request is given by three integers $c_i,L_i,R_i$, where $c_i$ is the delegation number, and $L_i$ and $R_i$ are the first and last position numbers on the stage that delegation $c_i$’s students should occupy. All $c_i$ must be distinct. If there are multiple solutions, you may output any one of them.

Explanation of sample $1$: If delegations’ students come onto the stage in the order given in the output, then after each delegation comes up, the students on the stage should be arranged as follows: 1. $4\ 4\ 4\ 4\ 4\ 4\ 4$; 2. $4\ 7\ 7\ 7\ 4\ 4\ 4$; 3. $10\ 10\ 10\ 10\ 4\ 4\ 4$; 4. $10\ 5\ 5\ 10\ 4\ 4\ 4$; 5. $10\ 5\ 5\ 10\ 4\ 2\ 4$. | Subtask | Score | $m\le$ | $n\le$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $15$ | $100$ | $100$ | | $2$ | $15$ | $10^4$ | $10^4$ | | $3$ | $5$ | $3\times10^5$ | $2$ | | $4$ | $5$ | $3\times10^5$ | $3$ | | $5$ | $20$ | $3\times10^5$ | $10$ | | $6$ | $40$ | $3\times10^5$ | $3\times10^5$ | Translated by ChatGPT 5