Sim-4-1 | catelusi

Daniel și-a deschis o "grădiniță" și are în grija sa $N$ cățeluși de diferite vârste pe care i-a dresat să stea într-un cerc. Cățelușii sunt numerotați de $1$ la $N$ și pentru fiecare cățeluș $i$ cu valori între $1$ și $N$ cunoaștem vârsta sa $V_i$. Fiecare cățeluș $i$ îi are ca vecini pe cățelușii $i − 1$ și $i + 1$. Dat fiind că ei stau într-un cerc, cățeii de pe pozițiile $1$ și $N$ sunt de asemenea vecini.

Daniel trebuie să țină cățelușii concentrați pentru câteva ore și decide să se joace un joc cu ei. Pentru jocul ales de Daniel e necesar să împartă cățelușii în echipe de câte $K$ cățeluși puși în ordine consecutivă în cerc. Deoarece cățeii au vârste diferite ea vrea să aleagă un $K$ astfel încât echipele să fie cât mai echilibrate. Pentru a evalua cât de echilibrată va fi împărțirea în echipe de câte $K$ el calculează un coeficient de echilibru astfel:

• Alege toate subsecvențele de câte $K$ cățeluși consecutivi
• Alege minimul din fiecare subsecvență
• Alege maximul dintre aceste minime, coeficientul de echilibru

El ar vrea ca respectivul coeficient să fie cât mai mare, dar să rămână mai mic strict decât o valoare $S$ dată.

Ajutați-l pe Daniel să găsească numărul $K$ pentru care se obține cel mai mare coeficient de echilibru mai mic strict decât $S$. Dacă există mai multe valori $K$ pentru care se obține rezultatul ideal, se va afișa cel mai mare dintre ele.

Cerință

Dându-se $N$, $S$ și vârstele cățelușilor, să se afle cel mai mare număr $K$ pentru care se obține coeficientul de echilibru ideal.

Date de intrare

Pe prima linie se află două numere naturale $N$ și $S$, separate printr-un spațiu, cu semnificația din enunț. Pe a doua linie a fișierului de intrare se află $N$ numere naturale separate prin câte un spațiu, $V_1, V_2, \dots, V_N$, reprezentând vârstele cățelușilor în ordinea în care sunt așezați în cerc.

Date de ieșire

Se va afișa un singur număr natural, $K$, rezultatul cerut.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq K \leq N$
• $0 \leq S, V_i \leq 1 \ 000 \ 000 \ 000$
• Se garantează că există cel puțin un cățelus, cu vârsta mai mică decât $S$.

  #	Punctaj	Restricții
  1	26	$1 \leq N \leq 1 \ 000$
  2	31	$1 \leq N \leq 100 \ 000$
  3	43	Fără restricții suplimentare

Exemplul 1

stdin

5 3
1 2 3 4 5

stdout

4

Explicație

Luăm toate subsecvențele de cățeluși de lungime $4$:
$1 \ 2 \ 3 \ 4 \rightarrow$ minimul este $1$
$2 \ 3 \ 4 \ 5 \rightarrow$ minimul este $2$
$3 \ 4 \ 5 \ 1 \rightarrow$ minimul este $1$
$4 \ 5 \ 1 \ 2 \rightarrow$ minimul este $1$
$5 \ 1 \ 2 \ 3 \rightarrow$ minimul este $1$
Valoarea maximă a unui minim este de $2$ ce este mai mic strict decât $3$.

Exemplul 2

stdin

4 3
2 4 2 4

stdout

4

Explicație

Luăm toate subsecvențele de cățeluși de lungime $4$:
$2 \ 4 \ 2 \ 4 \rightarrow$ minimul este $2$
$4 \ 2 \ 4 \ 2 \rightarrow$ minimul este $2$
$2 \ 4 \ 2 \ 4 \rightarrow$ minimul este $2$
$4 \ 2 \ 4 \ 2 \rightarrow$ minimul este $2$
Maximul este $2$ ce este mai mic strict decât $3$.
Luăm toate subsecvențele de lungime $3$:
$2 \ 4 \ 2 \rightarrow$ minimul este $2$
$4 \ 2 \ 4 \rightarrow$ minimul este $2$
$2 \ 4 \ 2 \rightarrow$ minimul este $2$
$4 \ 2 \ 4 \rightarrow$ minimul este $2$
Maximul este $2$ ce este mai mic strict decât $3$.
Luăm toate subsecvențele de lungime $2$:
$2 \ 4 \rightarrow$ minimul este $2$
$4 \ 2 \rightarrow$ minimul este $2$
$2 \ 4 \rightarrow$ minimul este $2$
$4 \ 2 \rightarrow$ minimul este $2$
Maximul este $2$ ce este mai mic strict decât $3$.
Remarcăm că obținem valoarea ideală pentru $K$ egal $2$, $3$ și $4$, dar deoarece în caz de egalitate alegem $K$ cel mai mare, răspunsul final este $4$.