Problem description
W pewnym magicznym królestwie słów i liczb żył młody bibliotekarz Bajtazar, którego zadaniem było rozwiązywanie zagadek zapisanych w pradawnych księgach. W tej krainie panowała osobliwa magia: litery wewnątrz słowa mogły być dowolnie poprzestawiane, a mimo to każdy bez trudu je odczytywał – wystarczyło, by pierwsza i ostatnia litera pozostały na swoim miejscu.
Podobna zasada dotyczyła ciągów liczbowych. Mówiła ona, że ciąg liczb całkowitych jest czytelny wtedy, gdy jego pierwszy element jest najmniejszy w całym ciągu, a ostatni – największy. W przeciwnym razie ciąg uznaje się za nieczytelny. Na przykład ciągi [1,3,2,4] i [1,2,1,2] są czytelne, a [1,3,2] i [2,1,2] nie są.
Bajtazar odkrył jednak sposób na odczytywanie ciągów nieczytelnych. Najpierw dzieli cały ciąg liczbowy na czytelne fragmenty, następnie odczytuje każdy z nich, a potem łączy uzyskane informacje w spójną całość. Oczywiście im mniej fragmentów trzeba połączyć, tym łatwiej. Pomóż Bajtazarowi rozszyfrować treść proroctwa i napisz program, który wczyta ciąg liczbowy oraz wypisze najmniejszą liczbę czytelnych fragmentów, na jaką można go podzielić.
Wejście
W pierwszym wierszu znajduje się jedna liczba całkowita N. W drugim i ostatnim wierszu wejścia znajduje się N liczb całkowitych ai pooddzielanych pojedynczymi odstępami i oznaczających kolejne wyrazy ciągu.
Wyjście
Twój program powinien wypisać tylko jedną liczbę całkowitą – najmniejszą liczbę czytelnych fragmentów, na jaką trzeba podzielić ciąg ai.
Ograniczenia
1 ≤ N ≤ 300 000, 1 ≤ ai ≤ 109.
Podzadania
| Podzadanie | Warunki | Punkty |
|---|---|---|
| 1 | ai ≤ 2 | 8 |
| 2 | N ≤ 20 | 12 |
| 3 | N ≤ 500 | 20 |
| 4 | N ≤ 5 000 | 30 |
| 5 | brak dodatkowych ograniczeń | 30 |
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Podział ciągu wygląda następująco: [2,3], [1,1,5], [1] |
| Wejście | Wyjście | Wyjaśnienie |
|
|
Podział ciągu wygląda następująco: [5], [4], [3], [2], [1] |
| Wejście | Wyjście | Wyjaśnienie |
|
|
Podział ciągu wygląda następująco: [1,3,2,4] |