Fie un şir a₁, a₂, ..., a_N de N numere întregi şi K un număr natural. O secvenţă a_i, a_i+1, a_i+2 ..., a_j din şir spunem că este K-secvenţă dacă există cel mult K numere strict mai mari decât a_i. De exemplu, pentru N=10, şirul a = 3,6,4,2,1,10,9,5,8,7 şi K=3, atunci 6,4,2,1,10,9,5,8 este K-secvenţă pentru că sunt exact 3 numere strict mai mari decât 6. La fel, 5,8,7 este K-secvenţă pentru că sunt doar două numere mai mari strict decât 5.

Cerinţă

Scrieţi un program care să determine cea mai lungă K-secvenţă a_i, a_i+1, a_i+2, ..., a_j din şir.

Date de intrare

Fişierul de intrare ksecv.in conţine pe prima linie numerele naturale N şi K, iar pe a doua linie elementele a₁ a₂ ... a_N ale şirului, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire ksecv.out va conţine pe prima linie linie două numere naturale i şi j separate printr-un spaţiu, reprezentând indicii de început şi de sfârşit ai K-secvenţei de lungime maximă. Dacă sunt mai multe soluţii, se va scrie aceea pentru care i este minim.

Restricţii

• 3 <= N <= 100 000
• 1 <= K <= N
• -10⁹ <= a_i <= 10⁹, pentru orice i între 1 şi N.

Exemplu

ksecv.in	ksecv.out	Explicaţii
10 3 3 6 4 2 1 10 9 5 8 7	2 9	Cea mai lungă 3-secvenţă este cea care începe la poziţia 2 şi se încheie la poziţia 9, adică 6 4 2 1 10 9 5 8, în această secvenţă existând 3 numere strict mai mari decât 6.

prof. Dan Pracsiu

Grupul Scolar "Stefan Procopiu" Vaslui

dpracsiu@yahoo.com