Fişierul intrare/ieşire:	cpr.in, cpr.out	Sursă	RMI 2016
Autor	Florin Chirica	Adăugată de	Bogdan Ciobanu •bciobanu
Timp execuţie pe test	0.05 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Cut-paste-reverse

Se consideră o listă de numere întregi (1, 2, ..., N) . Pe această listă puteţi efectua o serie de operaţii de tipul cut-paste. O operaţie de acest tip $<x, y, z>$ implică extragerea secvenţei dintre valorile x şi y şi inserarea acesteia imediat după valoarea z (sau la începutul listei în caz că z este 0). Acest triplet este considerat corect, dacă:

x apare înaintea lui y în listă, sau x = y.
z apare înafara secvenţei de la x la y, sau z = 0.

Găsiţi o serie de operaţii corecte pentru a răsturna lista, adică pentru a obţine lista (N, N-1, ..., 1). Cu cât mai puţine operaţii folosiţi, cu atât scorul va fi mai mare.

Date de intrare

Fişierul de intrare cpr.in va conţine pe prima linie numărul natural N, reprezentând lungimea listei.

Date de ieşire

Fişierul de ieşire cpr.out trebuie să conţină pe prima linie valoarea M, reprezentând numărul de operaţii cut-paste. Fiecare din următoarele M linii trebuie să conţină trei numere întregi x, y şi z, aferente operaţiei.

Restricţii

1 ≤ N ≤ 5.000
Se va acorda punctaj maxim pe test dacă $M \leq [\frac{N}{2}] + 1$ .
Se va acorda 80% din punctajul testului dacă $[\frac{N}{2}] + 1 < M \leq [\frac{2N}{3}]$ .
Se va acorda 60% din punctajul testului dacă $[\frac{2N}{3}] < M \leq [\frac{3N}{4}]$ .
Se va acorda 40% din punctajul testului dacă $[\frac{3N}{4}] < M \leq [\frac{4N}{5}]$ .
Se va acorda 20% din punctajul testului dacă $[\frac{4N}{5}] < M \leq [\frac{5N}{6}]$ .
Nu se va acorda nimic dacă se folosesc mai mult de $[\frac{5N}{6}]$ operaţii sau dacă operaţiile nu conduc la o listă răsturnată.

Exemplu

cpr.in	cpr.out
6	4 2 6 0 4 5 0 3 6 4 6 5 0

Explicaţie

Lista initială este (1 2 3 4 5 6).
În urmă primei operaţii, lista devine (2 3 4 5 6 1) (şi operaţia 1 1 6 ar fi avut acelaşi rezultat).
După cea de a doua operaţie, lista devine (4 5 2 3 6 1).
După cea de a treia operaţie, lista devine (4 3 6 5 2 1).
După cea de a patra operaţie, lista devine (6 5 4 3 2 1).

Această soluţie obţine punctaj maxim, întrucât s-au efectuat doar $4 = [\frac{6}{2}] + 1$ operaţii, iar lista a fost răsturnată.