Rezolvare PBinfo #2156

Pentru următorul an școlar admiterea celor N elevi în liceu se va face pe baza unor evaluări complexe. Fiecare dintre viitorii elevi ai clasei a IX-a va primi, în urma testelor și probelor pe care le va susține, un punctaj (număr natural nenul) cu care va participa la admiterea electronică.

Repartizarea fiecărui elev în clase se face în ordinea înscrierii respectând criteriile:

• Primul elev se repartizează în clasa cu numărul de ordine 1.
• În clasa în care este repartizat un elev nu există, până la momentul repartizării sale, nici un punctaj mai mare decât al său.
• Numărul claselor să fie cât mai mic posibil.

Cerințe

Determinaţi:

1. Punctajul primului elev care nu ar mai putea fi repartizat în prima clasă în condițiile în care toți elevii își doresc să fie repartizați în prima clasă(se aplică doar la cerința 1).
2. Numărul claselor ce se vor forma respectând criteriile.

Date de intrare

Fișierul de intrare adlic.in conține pe primul rând numărul C a cărui valoare poate fi 1 sau 2, apoi separat de un spațiu numărul natural N.

Pe liniile următoare se găsesc cele N punctaje ale elevilor în ordinea înscrierii, numere naturale nenule despărțite prin câte un spațiu.

Date de ieșire

Dacă C=1, atunci în fişierul de ieşire adlic.out se va scrie soluția cerinței 1.
Dacă C=2, atunci în fişierul de ieşire adlic.out se va scrie soluția cerinței 2.

Restricții și precizări

• Punctajele elevilor vor avea cel mult șase cifre
• 1 ≤ N ≤ 1 000 000
• Pentru cerința 1 se garantează existența soluției
• Pentru 20% din punctaj cerinţa va fi C = 1
• Pentru alte 20% din punctaj cerinţa va fi C = 2 și N ≤ 1000
• Pentru restul testelor C = 2 și N ≤ 1 000 000

Exemplul 1

adlic.in

1 9
4 2 4 2 7 10 9 11 8

adlic.out

2

Explicație

4 se repartizează în prima clasă, iar 2 trebuie repartizat în cea de-a doua clasă

Exemplul 2

adlic.in

2 9
4 2 4 2 7 10 9 11 8

adlic.out

3

Explicație

O soluție posibilă este cea în care se formează clasele:

4 4 7 9 
2 2 10 11
8