Algoritmul

Cerință

Tudor și Luca sunt doi tineri programatori. Aceștia tocmai au terminat un curs de algoritmică avansată în C și încearcă să rezolve probleme cât mai eficient. Una dintre problemele la care se gândesc cei doi spune asta:

• există un șir de $N$ biți consecutivi numerotați de la $1$ la $N$ care inițial sunt setați pe $0$
• treptat toți biții vor fi transformați în $1$ într-o ordine dată
• pentru fiecare bit transformat spuneți care sunt capetele celei mai lungi secvențe de $1$ din care bitul respectiv face parte

Cum Tudor a găsit soluția optimă într-un vis, Luca vă plătește să îi rezolvați și lui problema pentru a nu rămâne în urma prietenului său. Vă roagă să fiți foarte atenți datorită limitelor scăzute, cu cât mai ineficienți, cu atât mai puțini bani!!!

Date de intrare

Pe prima linie a fișierului de intrare algoritmul.in se găsesc un număr $N$ și un șir de $N$ numere $a_1, a_2, \dots, a_n$ reprezentând ordinea în care se transformă biții de pe pozițiile $a_i$.

Date de ieșire

Pe linia i a fișierului de ieșire algoritmul.out se vor găsi 2 valori, left și right reprezentând capetele secvenței din care bitul de pe poziția $a_i$ face parte.

Restricții și precizări

• $1 \leq N \leq 10 \ 000 \ 000$;
• Se acordă $20$ de puncte pentru $1 \leq N \leq 1 \ 000$;
• Se acordă $50$ de puncte pentru $1 \leq N \leq 5 \ 000 \ 000$;
• Testul 13 este exemplul așa că nu este punctat.
• Datorită volumului mare de date citite și scrise, folosiți fișierul de parsing de la atașamente din dreapta ecranului.

Exemplu

algoritmul.in

6
3 4 1 6 2 5

algoritmul.out

3 3
3 4
1 1
6 6
1 4
1 6

Explicație

După cum se vede, inițial bitul de pe poziția $3$ este transformat, 001000, deci secvența de care aparține este formată din el și persoana sa. După se transformă bitul $4$, 001100, deci secvența lui începe la $3$ și se termină la $4$. După se transformă primul bit, dar este singur deci este propria lui secvență, deci se afișează $1$ și $1$. Tot așa până terminăm cu bitul $5$ unde toți biții sunt legați deci secvența este chiar tot șirul deci startul este $1$ și finalul $6$.