Într-un institut de geologie se folosesc mai multe tipuri de roci pentru analize spectrale. Rocile sunt păstrate în n recipiente, numerotate distinct de la 1 la n, în ordinea colectării. Pentru efectuarea unui experiment se alege numărul maxim de roci, în ordinea în care au fost colectate, astfel încât numerele de minerale din compoziţia rocilor alese să fie consecutive, ordonate strict crescător.

Cerinţă

Dat fiind n, numărul de roci şi numărul de minerale conţinute de fiecare rocă, în ordinea colectării acestora, să se determine numărul minim de experimente care se pot efectua astfel încât să fie folosite toate rocile.

Date de intrare

Fişierul de intrare roci.in conţine pe prima linie un număr natural n reprezentând numărul de roci. Pe cea de a doua linie se află n numere naturale nenule, separate prin câte un spaţiu, m₁ m₂ … m_n, reprezentând numărul de minerale conţinute de fiecare rocă.

Date de ieşire

Fişierul de ieşire roci.out va conţine o singură linie pe care va fi scris un număr natural G reprezentând numărul minim de grupe de roci care se pot forma.

Restricţii

• 0<n≤100000
• 0<m_i≤10000, pentru 1≤i≤n
• Numărul de minerale conţinute poate fi acelaşi pentru roci diferite.
• O rocă poate fi folosită într-o singură grupă.

Exemplu

roci.in	roci.out	Explicaţii
7 3 10 4 4 5 11 6	3	Se formează grupele: 3 4 5 6 10 11 4

prof. Simona Ingrid Iuscinschi

Liceul de Informatică „Grigore Moisil” Iaşi