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ța

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 ≤ N ≤ 500.000
• 1 ≤ M ≤ 500.000
• 1 ≤ K ≤ M
• 1 ≤ înălțime cui ≤ 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.