Fişierul intrare/ieşire:	rotatii.in, rotatii.out	Sursă	Lot Deva 2013 - Baraj 3 Seniori
Autor	Adrian Budau	Adăugată de	Rares Buhai •darren
Timp execuţie pe test	0.3 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Rotatii

Tractorel s-a gândit un pic, pic la o problemă în timp ce ploua cu adrese intr-o dimineaţă. El se gândeşte serios la un şir de N numere întregi având la stânga dolărei şi la dreapta leii grei. Deoarece Tractorel deţine puteri supranaturale, el poate efectua următoarele operaţii asupra şirului:

• Insert (X Y) – inserează în şir elementul cu valoarea Y după elementul de pe poziţia X (dacă X este 0, Y se inserează la inceputul şirului)
• Delete K – se elimină elementul de pe poziţia K din şir
• Query

Tractorel consideră că un şir are proprietea de Minune dacă toate elementele şirului de sume parţiale care încep de la primul element sunt nenegative. La operaţia de tip Query, Tractorel vă roagă frumos să determinaţi o permutare circulară a şirului astfel încât acesta să aibă proprietatea de Minune. Spre exemplu, dacă avem şirul S = [1, -1, 2, 5] acesta se poate permuta circular in şirurile S0 = [1, -1, 2, 5], S1 = [-1, 2, 5, 1], S2 = [2, 5, 1, -1], S3 = [5, 1, -1, 2] iar şirul sumelor parţiale asociat acestor şiruri este: S0’ = [1, 0, 2, 7], S1’ = [-1, 1, 6, 7], S2’ = [2, 7, 8, 7], S3’ = [5, 6, 5, 7]. Se observă că şirurile S0, S2, S3 respectă proprietatea de şiruri Minune.

Tractorel, fiind modest, nu doreşte decât afişarea unui singur număr la operaţia de tip Query, anume cu câte poziţii trebuie să permute circular şirul S spre stânga pentru ca acesta să aibă proprietatea de şir Minune. Un răspuns corect la o operaţie Query pe S = [1, -1, 2, 5] este 3 pentru că şirul obţinut prin permutarea circulară a lui S de 3 ori la stânga este S3, care este un şir Minune.

În caz că nu există nici un şir minune în toate permutările circulare ale şirului, se va afişa -1.

Cerinţă

Pentru un şir conţinând iniţial N numere întregi şi M operaţii de tipul Insert (X Y), Delete K, Query. personajul principal doreşte să afişati răspunsul la toate intrebările de tip Query.

Date de intrare

În fişierul de intrare rotatii.in, pe prima linie se află 2 numere intregi N şi M, iar pe a 2-a linie se află N numere intregi. După linia 2 urmează M linii, reprezentând operaţiile codificate in felul următor:

• 0 X Y – Insert (X, Y)
• 1 K – Delete
• 2 – Query

Date de ieşire

În fişierul de ieşire rotatii.out se va afişa raspunsul la fiecare query câte un număr pe linie reprezentând numărul de poziţii cu care trebuie rotit şirul sau -1 dacă nu există soluţie.

Restricţii

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 100000
• 0 ≤ X, K ≤ numărul curent de elemente din şir
• Şirul conţine numere întregi din intervalul [-10⁹, 10⁹]

Exemplu

Explicaţie

La primul query sirul are forma 2 -3 5 2 -100 şi pentru nicio permutare circulară nu avem proprietatea de şir Minune. Mai departe analizaţi :).

Cum se trimit solutii?