I gospođa, ​ ​gospođica, ​ ​kako ​ ​će ​ ​da ​ ​kaže: "Ja ​ ​jašem​ ​konje ​ ​petnaest ​ ​godina, ​ ​konja ​ ​je ​ ​nemoguće ​ ​potkovati ​ ​naopako!"

(...)

"Da, to je naopako" - prošapće Domagoj, gledajući karte u ruci suigrača Mate u za potrebe ovog zadatka značajno izmijenjenoj kartaškoj igri Hanabi. Radi jednostavnosti, suigrač Mate u ruci drži \(​N\) karata s brojevima \(1, 2, \ldots, ​N\) u nekom poretku. (Svaki broj od \(1\) do \(​N\) pojavljuje se ​ ​točno ​ ​jednom).​ ​Kao ​ ​i ​ ​u ​ ​pravoj ​ ​igri, ​ ​ne ​ ​smije ​ ​svojevoljno ​ ​mijenjati ​ ​njihov​ ​poredak.

Kako bi kraj teksta zadatka imao bar malo veze s pričom, Domagoj će svome suigraču Mati pokazati na jedan uzastopni podniz karata. (Možda će pokazati samo i na jednu kartu, ali će pokazati barem na jednu kartu.) Suigrač Mate će tada "okrenuti" taj uzastopni podniz i vratiti ga ​ ​na ​ ​mjesto.

Okretanje se može zamisliti kao uzimanje i rotacija za \(180\) stupnjeva svih karata odabranog podniza zajedno. Okretanjem prva i posljednja karta podniza zamijene mjesta, kao i druga i pretposljednja, ​i ​tako ​dalje.

Kao i svi mi, Domagoj jako voli fiksne točke, tj. karte kojima se broj koji piše na njima podudara s njihovim mjestom u ruci brojeći Domagoju slijeva. Zato želi da broj fiksnih točaka nakon ​ ​okretanja ​ ​izabranog ​ ​podniza ​ ​bude ​ ​što ​ ​veći.

Pomozite Domagoju saznati na koji uzastopni podniz mora pokazati kako bi broj fiksnih točaka ​ ​u ​ ​ruci ​ ​suigrača ​ ​Mate ​ ​nakon ​ ​okretanja ​ ​tog ​ ​podniza ​ ​bio ​ ​najveći.

Ulazni podaci

U​ ​prvom​ ​retku ​ ​nalazi ​ ​se ​ ​prirodan ​ ​broj​ \(​​N\)​ \(​(1 \leq​ ​​N​ ​\leq ​500 ​ ​000)\), ​ ​broj ​ ​karata ​ ​u ​ ​ruci ​ ​suigrača ​ ​Mate.

U sljedećem retku nalaze se brojevi na kartama u Matinoj ruci redoslijedom kojim ih vidi Domagoj.

Izlazni podaci

U jednom retku ispišite ​\(A\) i \(​B\) ​, brojeve koji pišu na kartama koje su redom početak i kraj traženog ​ ​uzastopnog ​ ​podniza. ​ ​Ako ​ ​postoji ​ ​više ​ ​mogućnosti, ​ ​ispišite ​ ​bilo ​ ​koju.

Bodovanje

U​ ​test ​​podacima ​​ukupno ​vrijednima ​ ​\(30\%\)​ ​bodova ​​vrijedit ​će \(​​​N​ ​\leq ​500\).

U​ ​test ​​podacima​ ​ukupno ​vrijednima ​ ​dodatnih ​\(​30\%\)​ ​bodova ​ ​vrijedit ​ ​će ​\(​​N​ \leq​ ​5000\).

Primjeri test podataka

Ulaz

4 3​
2 ​1 ​4

Izlaz

3 1

Objašnjenje

U prvom test primjeru će nakon okretanja uzastopnog podniza koji počinje s \(3\) i završava s \(1\) karte biti poredane ​ \(​1 ​ ​2 ​ ​3 ​ ​4\), ​ ​i ​ ​sada ​ ​su ​ ​sve ​ ​karte ​ ​fiksne ​ ​točke. ​ ​U ​ ​ovom​ ​primjeru ​ ​je ​ ​dani ​ ​izlaz​ ​jedini ​ ​točan ​ ​izlaz.

Ulaz

2
1 2

Izlaz

1 1

Objašnjenje

U drugom test primjeru, okretanje bilo kojeg podniza sastavljenog od samo jedne karte rezultira istim rasporedom, ​ ​koji ​ ​daje ​ ​najveći ​ ​broj ​ ​fiksnih ​ ​točaka.

Ulaz

7
3​ ​6​ ​5​ ​7​ ​4​ ​1​ ​2

Izlaz

3 2