permsort

Cerință

Se dă o permutare cu $N$ elemente. Asupra permutării pot fi efectuate două tipuri de mutări:

• Alegerea unui prefix și inversarea lui.
• Alegerea unui sufix și inversarea lui.

Vi se cere să sortați crescător permutarea folosind operațiile descrise. Pentru a obține toate punctele aveți voie să efectuați maximum $2 \cdot N$ operații.

Date de intrare

Fişierul permsort.in conţine pe prima linie numărul $N$, iar pe următoarea linie $N$ valori reprezentând o permutare.

Date de ieșire

Fişierul de ieşire permsort.out va conţine pe prima linie numărul $M$ de operații efectuate. Următoarele 4M$ linii vor conține descrierea operațiilor efectuate astfel:

• Dacă se dorește inversarea prefixului care se termină la o anumită poziție se va afișa caracterul P urmat de valoarea poziției.
• Dacă se dorește inversarea sufixului care se începe la o anumită poziție se va afișa caracterul S urmat de valoarea poziției.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• Dacă $M \leq 2 \cdot N$ veți obține punctaj maxim.
• Dacă $2 \cdot N < M \leq 5 \cdot N$ veți obține $50\%$ din punctaj.
• Pentru $M > 5 \cdot N$ nu se vor acorda puncte.
• Pentru $70\%$ din teste, $N \leq 200 \ 000$

Exemplu

permsort.in

6
6 5 4 1 2 3

permsort.out

2
S 4
P 6

Explicație

După prima operație permutarea devine: $6 \ 5 \ 4 \ 3 \ 2 \ 1$. A două operație inversează tot șirul, iar permutarea devine sortată.