Pentru orice şir de numere S numim subsecvenţă a şirului orice succesiune neîntreruptă de elemente din şir Si Si+1... Si+lg-1. O subsecvenţă este unic determinată de poziţia primului element al său (i) şi de lungimea sa (lg). O subsecvenţă este crescătoare dacă toate elementele sale sunt în ordine crescătoare Si<=Si+1<...<Si+lg-1.
De exemplu, pentru şirul cu 5 elemente 2 1 3 4 4, subsecvenţa crescătoare cu cele mai multe elemente este cea care începe cu al doilea element din şir şi are lungimea 4, adică 1 3 4 4.
Cerinţă
Fiind dat un şir de numere întregi se cere să se determine cea mai lungă subsecvenţă crescătoare din şir. În cazul în care există mai multe subsecvenţe de lungime maximă se va afişa doar prima dintre acestea, adică subsecvenţa care are indicele de început minim.
Date de intrare
Fişierul de intrare subsecvmax.in conţine pe prima linie numărul natural n, iar pe cea de a doua linie cele n numere întregi reprezentând elementele şirului.
Date de ieşire
Fişierul de ieşire subsecvmax.out va conţine două numere naturale i lg, separate printr-un spaţiu cu semnificaţia din enunţ (i este poziţia de început a subsecvenţei de lungime maximă, iar lg este lungimea acesteia).
Restricţii
• 1 ≤ n ≤ 100 000
• Elementele şirului sunt numere întregi aparţinând intervalului [-1 000 000,1 000 000]
• Indicele primului element din şir este egal cu 1.
Exemple
subsecvmax.in
subsecvmax.out
Explicaţii
11
10 1 3 5 2 4 6 10 7 8 9
5 4
Pentru şirul dat subsecvenţa de lungime maximă începe la poziţia 5 şi are în componenţă 4 elemente (2 4 6 10).