cuie

Pe o scândură se găsesc înfipte și aliniate $N$ cuie de diverse înălțimi, măsurate în centimetri. La fiecare ”bătaie” de ciocan într-un cui, acesta pătrunde în scândură cu $1$ cm. Tâmplarul dorește să obțină cea mai lungă secvență de cuie de aceeași înălțime, după aplicarea a cel mult $M$ ”bătăi” de ciocan.

Cerință

Să se determine lungimea maximă - $L$ a unei secvențe de cuie de aceeași înălțime în condițiile date și numărul minim de ”bătăi” - $K$ necesare obținerii acesteia.

Date de intrare

Fișierul de intrare cuie.in conține pe prima linie două numere naturale nenule $N$ și $M$ și pe următoarea linie $N$ valori naturale nenule ce reprezintă înălțimile celor $N$ cuie măsurate în cm.

Date de ieșire

Fișierul de ieșire cuie.out va conține pe prima linie, două numere naturale nenule $L$ și $K$, separate printr-un spațiu, ce reprezintă: $L$ - lungimea maximă a unei secvențe de cuie cu aceeași înălțime, respectiv $K$ - numărul minim de ”bătăi” de ciocan necesare pentru obținerea secvenței maxime.

Restricții și precizări

• $1 \leq N \leq 500 \ 000$
• $1 \leq M \leq 500 \ 000$
• $1 \leq K \leq M$
• $1 \leq$ înălțime cui $\leq 100 \ 000$ cm
• înălțimea unui cui reprezintă lungimea părții aflate în afara scândurii.

Exemplu

cuie.in

8 5
3 2 4 3 3 5 3 1

cuie.out

5 3

Explicație

Secvența de lungime maximă se obține după $3$ ”bătăi”, efectuate asupra cuielor $3$ și $6$. $3 \ 2 \ 3 \ 3 \ 3 \ 3 \ 3 \ 1$.