Василько і комп'ютер#502
Sign in

Василько і комп'ютер

1 second
256 megabytes
Hard

Одного разу, блукаючи інтернетом, Василько натрапив на дивний комп'ютер, в котрому пам'ять мала вигляд стека, і вирішив його купити.

Коли той комп'ютер прийшов до нього, він помітив, що в подарунку до комп'ютера був масив довжини . Йому стало цікаво, на яку мінімальну кількість підмасивів потрібно поділити , щоб кожен підмасив можна було відсортувати на цьому комп'ютері.

Масив можна відсортувати на тому комп'ютері, якщо йти по ньому зліва направо і додавати елементи на верх пам'яті в вигляді стека. У будь-який момент можна викласти один елемент з верху пам'яті у фінальну послідовність. Проте, не обов'язково додати лише одне число зі стека у масив між проходами. Масив можна відсортувати, якщо можна зробити фінальну послідовність відсортованою.

Наприклад, масив [4, 2, 3, 7, 4, 5] можна відсортувати так:

  1. додаємо число у стек, зараз стек виглядає так , а масив так ;

  2. додаємо число у стек, зараз стек виглядає так , а масив так ;

  3. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так ;

  4. додаємо число у стек, зараз стек виглядає так , а масив так ;

  5. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так ;

  6. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так [2, 3, 4];

  7. додаємо число у стек, зараз стек виглядає так , а масив так [2, 3, 4];

  8. додаємо число у стек, зараз стек виглядає так , а масив так [2, 3, 4];

  9. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так [2, 3, 4, 4];

  10. додаємо число у стек, зараз стек виглядає так , а масив так [2, 3, 4, 4];

  11. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так [2, 3, 4, 4, 5];

  12. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так [2, 3, 4, 4, 5, 7].

Input

Перший рядок містить одне ціле число (1 \le n \le 10^6) — довжина масиву .

Другий рядок містить цілих чисел a_{1}, a_2, \dots, a_{n} (0 \le a_{i} \le 10^9) — значення елементів масиву .

Output

Виведіть одне ціле число, відповідь на задачу, на яку мінімальну кількість підмасивів потрібно поділити , щоб кожен можна було посортувати.

Examples

Example 1

Loading
Loading

Note

Масив [4, 2, 3, 7, 4, 5, 3, 1, 2, 5], можна поділити на [4, 2, 3, 7, 4, 5] та [3, 1, 2, 5], кожен з котрих можна посортувати на комп'ютері Василька.

Як можна відсортувати перший масив було пояснено раніше.

Другий масив ([3, 1, 2, 5]) можна відсортувати так:

  1. додаємо число у стек, зараз стек виглядає так , а масив так ;

  2. додаємо число у стек, зараз стек виглядає так , а масив так ;

  3. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так ;

  4. додаємо число у стек, зараз стек виглядає так , а масив так ;

  5. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так ;

  6. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так [1, 2, 3];

  7. додаємо число у стек, зараз стек виглядає так , а масив так [1, 2, 3];

  8. забираємо зі стека та додаємо у масив, зараз стек виглядає так , а масив так [1, 2, 3, 5].

Scoring

  1. ( балів): n \le 10^3;

  2. ( балів): a_{i} \le 1;

  3. ( балів): a_{i} \le 2;

  4. ( балів): a_{i} \le 5;

  5. ( балів): Відповідь не перевищує ;

  6. ( балів): без додаткових обмежень.