Сучасне мистецтво 2

Picowso вирішила перейти на 1-вимірний стиль.

Тепер її картини можна описати як 1-вимірний масив кольорів довжини n. Її стиль залишився незмінним: вона починає з пустого полотна і малює відрізками. Кожен з кольорів від 1 до n використовується рівно один раз, хоча деякі кольори можуть бути повністю приховані до завершення малювання.

Moonet, суперник Picowso, знайшов спосіб копіювати її картини. Він малює набір незв'язаних інтервалів. Moonet може малювати не більше одного інтервалу кожного кольору протягом всього процесу. Порахуйте, скільки раундів потрібно Moonet, щоб скопіювати 1-вимірну картину Picowso.

Вхідні дані

Перша стрічка містить n (1 ≤ n ≤ 10^5), а наступні n стрічок містять ціле число в діапазоні від 0 до n, що вказує колір кожної комірки на 1-вимірному полотні (0 для пустої комірки).

Вихідні дані

Виведіть мінімальну кількість раундів, необхідну для копіювання заданого малюнка, або -1, якщо неможливо відтворити цей малюнок у стилі, автентичному стилю Picowso (тобто, його не можна намалювати шарами послідовностей інтервалів, по одному для кожного кольору).

Приклади

Примітка

У цьому прикладі інтервал кольору 1 повинен бути намальований раніше раундів для кольорів 4 і 5, тому потрібно як мінімум 2 раунди.