Diferențe pentru problema/gogosi între reviziile #1 si #2

== include(page="template/taskheader" task_id="gogosi") ==

Poveste și cerință...

La magazinul X sunt N persoane așezate la coadă pentru gogoși. Din cauza aglomerației, managerul
vrea să împartă persoanele la mai multe case. Deoarece toată lumea trebuie să vadă gogoșile,
înălțimea fiecărei persoane trebuie să fie mai mică sau egală decât înălțimile tuturor celor de după el în
coadă lui. Mai mult, dacă persoana i în șirul inițial și persoana j în șirul inițial (i < j) ajung în aceeași
coadă, persoană i trebuie să fie înaintea persoanei j. Dându-se N, numărul de persoane și A, înălțimile
persoanelor în ordinea inițială, să se afișeze numărul minim de case pe care managerul trebuie să le
deschidă.

h2. Date de intrare

Fișierul de intrare $gogosi.in$ ...

În fișierul $gogosi.in$ se află pe prima linie numarul N iar pe a doua line N numere naturale, A[~i~]
reprezentând înălțimea persoanei i din coadă inițială.

h2. Date de ieșire

În fișierul de ieșire $gogosi.out$ ...

Afișați pe prima linie din fișierul $gogosi.out$ numărul minim de case care trebuie deschise.

h2. Restricții

* $... ≤ ... ≤ ...$

* 1 ≤ N ≤ 10[^6^]
* 1 ≤ A[~i~] ≤ 10[^5^]
* 1 ≤ A[~i~] ≤ 2 pentru teste în valoare de 20 puncte.
* 1 ≤ N ≤ 103 pentru teste în valoare de alte 30 puncte.

h2. Exemplu
table(example).

|_. gogosi.in |_. gogosi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|

|_. gogosi.in |_. gogosi.out |_. Explicații |
| 7
1 4 2 3 9 7 6
| 3
| Numărul minim de case care trebuie deschise este
3. Există mai multe variante de a împărți
persoanele, una dintre acestea este:
Coada 1:
i 1 2 5 (persoanele din sirul initial)
A[i] 1 4 9 (inaltimile lor)
Coada 2:
i 3 6 (persoanele din sirul initial)
A[i] 2 7 (inaltimile lor)
Coada 3:
i 4 7 (persoanele din sirul initial)
A[i] 3 6 (inaltimile lor)
| 5
1 2 1 1 2
| 2
| Numărul minim de case care trebuie deschise este
2. Una dintre variante este:
Coada 1:
i 1 2 (persoanele din sirul initial)
A[i] 1 2 (inaltimile lor)
Coada 2:
i 3 4 5 (persoanele din sirul initial)
A[i] 1 1 2 (inaltimile lor)
|

h3. Explicație