D — Lapjárás

„Igen, ez fordítva van” – súgta Domagoj a Mate kezében lévő kártyákat figyelve, miközben a Hanabi nevű kártyajáték egy erősen módosított változatát játszották. Az egyszerűség kedvéért tegyük fel, hogy Mate N kártyát tart a kezében, amelyeket az 1, 2, …, N számok egy bizonyos sorrendjével írunk le. (Minden szám 1-től N-ig pontosan egyszer fordul elő.) Ahogy a valós játékban is, Mate nem rendezheti át önkényesen a kezében lévő kártyákat.

Hogy a feladat legalább egy kicsit kapcsolódjon a történethez, Domagoj kijelöli a Mate kezében lévő kártyák egy összefüggő részsorozatát. (Egyetlen kártyát is kijelölhet, de legalább egyet biztosan.) Mate ezután „megfordítja” ezt az összefüggő részsorozatot, majd visszateszi a helyére. (A forgatást úgy kell érteni, hogy veszi az adott részsorozat összes kártyáját, majd megcseréli az elsőt az utolsóval, a másodikat az utolsó előttivel és így tovább.)

Fix pontnak nevezzük azt a kártyát, amelynek a száma megegyezik a pozíciójával, ha Domagoj bal oldala felől nézzük. Mint mindannyiunk, Domagoj is imádja a fix pontokat. Azt szeretné tehát, hogy a fix pontok száma a lehető legnagyobb legyen, miután megfordíttatja Matéval a kijelölt részsorozatot.

Segíts Domagojnak megtalálni azt az összefüggő részsorozatot, amelyet ki kell jelölnie ahhoz, hogy a Mate kezében lévő fix pontok száma maximális legyen a részsorozat megfordítását követően!

A bemenet specifikációja

A bemenet első sora egy N pozitív egész számot tartalmaz (1 ≤ N ≤ 500 000), amely a Mate kezében lévő kártyák számát adja meg.

A következő sor tartalmazza a Mate kezében lévő kártyákon szereplő számokat abban a sorrendben, ahogyan Domagoj látja őket.

A kimenet specifikációja

Egyetlen sort kell a kimenetre írni, amely a kérdéses összefüggő részsorozat első és utolsó kártyáján látható számokat tartalmazza, ebben a sorrendben, egy szóközzel elválasztva. Ha több jó megoldás is létezik, bármelyik megadható.

1. példa bemenet

1. 4
2. 3 2 1 4

letöltés szöveges állományként

Az 1. példa bemenethez tartozó kimenet

1. 3 1

letöltés szöveges állományként

2. példa bemenet

1. 2
2. 1 2

letöltés szöveges állományként

A 2. példa bemenethez tartozó kimenet

1. 1 1

letöltés szöveges állományként

3. példa bemenet

1. 7
2. 3 6 5 7 4 1 2

letöltés szöveges állományként

A 3. példa bemenethez tartozó kimenet

1. 3 2

letöltés szöveges állományként

A példák magyarázata

Az első tesztesetnél, miután megfordítjuk a 3-assal kezdődő és 1-essel végződő összefüggő részsorozatot, a kártyák sorrendje 1 2 3 4 lesz, így minden kártya fix pont lesz. Ebben az esetben a megadott kimenet az egyetlen helyes megoldás.

A második tesztesetnél bármelyik egy kártyából álló részsorozat megfordítása ugyanazt a kártyasorrendet eredményezi, azt, amelyik a maximális számú fix pontot tartalmazza.

Eredeti feladat

Croatian Open Competition in Informatics 2017/2018, Contest #2, Doktor