Для набора целых чисел \(S\) определим \(\operatorname{mex}(S)\) как наименьшее неотрицательное целое число, которое не встречается в \(S\).
Гражданин НИТ решил уничтожить вселенную. К сожалению, он не настолько могуществен, как Танос, так что для достижения своей цели ему придётся щёлкнуть пальцами несколько раз.
Вселенная может быть представлена массивом \(a\) длины \(n\) в 1-индексации. Когда НИТ щёлкает пальцами, он осуществляет следующую операцию над массивом:
- Он выбирает целые числа \(l\) и \(r\), такие что \(1\le l\le r\le n\). Пусть \(w=\operatorname{mex}(\{a_l,a_{l+1},\dots,a_r\})\). Тогда для всех \(l\le i\le r\) нужно заменить \(a_i\) на \(w\).
Будем говорить, что вселенная уничтожена, если и только если \(a_i=0\) для всех \(1\le i\le n\).
Найдите наименьшее количество действий, необходимое НИТу для уничтожения вселенной. Другими словами, найдите наименьшее число операций, в результате которых все элементы массива станут равны \(0\).
Выходные данные
Для каждого набора входных данных выведите одно число — ответ на задачу.
Примечание
В первом наборе входных данных все элементы массива изначально равны \(0\), так что достаточно сделать \(0\) операций.
Во втором наборе входных данных одним из оптимальных решений будет выбор одной операции с \(l=2\), \(r=5\).
В третьем наборе входных данных одним из оптимальных решений будет выбор двух операций с параметрами \(l=4\), \(r=4\) и \(l=2\), \(r=6\) соответственно.
В четвёртом наборе входных данных одним из оптимальных решений будет выбор одной операции с \(l=1\), \(r=1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
0 0 0 0
5
0 1 2 3 4
7
0 2 3 0 1 2 0
1
1000000000
|
0
1
2
1
|