Se cunosc înălțimile a N vârfuri, plasate de la stânga la dreapta, în cadrul unui lanț muntos. Dacă plasăm o santinelă pe un vârf de o anumită înălțime, aceasta veghează vârful respectiv și maximum K vârfuri la stânga și maximum K vârfuri la dreapta acestuia, dar cu condiția ca înălțimile acestor vârfuri vegheate să fie mai mici sau egale cu înălțimea vârfului pe care se află santinela. Dacă există un vârf cu o înălțime strict mai mare la distanță mai mică sau egală cu K, atunci santinela veghează doar până la acel vârf (exclusiv acel vârf).

Cerința

Date fiind N, K și înălțimile celor N vârfuri, să se determine:

• Numărul maxim de vârfuri consecutive, începând de la primul vârf al lanțului muntos (inclusiv acest vârf), ce pot fi vegheate cu o singură santinelă.
• Numărul minim de santinele necesare ca toate vârfurile să fie vegheate.

Date de intrare

Fișierul de intrare santinele.in conține pe prima linie numărul cerinței, 1 sau 2. Pe a doua linie, fișierul conține numerele N și K, cu semnificația din enunț. Pe a treia linie, fișierul conține N numere, h[1], h[2], ..., h[N], reprezentând înălțimile celor N vârfuri, în ordinea dispunerii lor de la stânga la dreapta, în cadrul lanțului muntos. Numerele aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire santinele.out va conține un singur număr. Dacă cerința este 1, conține numărul maxim de vârfuri determinate la această cerință. Dacă cerința este 2, conține numărul minim de santinele determinate la această cerință.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 0 ≤ K < N
• 1 ≤ h[i] ≤ 1.000.000
• Pentru 14 puncte, C = 1
• Pentru 14 puncte, C = 2, N este par și K = N / 2
• Pentru 16 puncte, C = 2 și h[1] < h[2] < ... < h[N]
• Pentru 13 puncte, C = 2 și există 1 < p < N pentru care h[1] < h[2] < ... < h[p-1] < h[p] > h[p+1] > ... > h[N]
• Pentru 14 puncte, C = 2 și N ≤ 15
• Pentru 29 puncte, fără restricții suplimentare

Exemplul 1:

santinele.in

1
8 2
6 10 5 7 8 5 4 4

santinele.out

4

Exemplul 2:

santinele.in

2
10 2
10 5 5 10 6 7 4 1 6 7

santinele.out

4

Exemplul 3:

santinele.in

2
15 3
5 3 1 12 11 9 15 11 10 9 2 7 10 11 7

santinele.out

3

Exemplul 4:

santinele.in

2
20 5
7 12 23 21 20 24 28 21 4 16 27 1 6 8 20 3 3 5 11 5

santinele.out

3

Explicații ale exemplelor

Primul exemplu: Cerința este 1 și K = 2. Santinela veghează vârful pe care este plasată, maximum două vârfuri la stânga și maximum două vârfuri la dreapta. Cu o singură santinelă putem acoperi maximum patru vârfuri, începând cu primul vârf, plasând santinela pe al doilea vârf.

Al doilea exemplu: Cerința este 2 și K = 2. Sunt necesare minimum 4 santinele, pe care le putem amplasa pe vârfurile: primul, al 4-lea, al 7-lea, al 10-lea.

Al treilea exemplu: Cerința este 2 și K = 3. Sunt necesare minimum 3 santinele. Le putem amplasa pe vârfurile: primul, al 7-lea, al 14-lea.

Al patrulea exemplu: Cerința este 2 și K = 5. Sunt necesare minimum 3 santinele. Le putem amplasa pe vârfurile: al 3-lea, al 7-lea, al 15-lea.