Дракон Эвирир пробрался в замок волшебника и нашел таинственное приспособление. Врожденные инстинкты дракона заставили его поиграть с приспособлением (уничтожить его)...
Дракон Эвирир нашел массив длины \(n\) из целых неотрицательных чисел \(a_1, a_2, \ldots, a_n\).
За одну операцию он может выбрать непустой подмассив\(^{\text{∗}}\) \(b\) массива \(a\) и заменить его одним числом — значением \(\operatorname{mex}(b)\)\(^{\text{†}}\). Он хочет использовать эту операцию некоторое количество раз, чтобы в результате массив \(a\) состоял только из нулей. Можно доказать, что это всегда возможно при заданных ограничениях.
Каково минимальное количество операций, необходимое для достижения цели?
Выходные данные
Для каждого набора входных данных выведите на отдельной строке минимальное количество операций, необходимых для получения массива \(a\), который содержит только нули.
Примечание
В первом наборе входных данных Эвирир может выбрать подмассив \(b = [1, 2, 3]\) и заменить его на \(\operatorname{mex}(1, 2, 3) = 0\), изменив \(a\) с \([0, \underline{1, 2, 3}]\) на \([0, 0]\) (где выбранный подмассив подчеркнут). Следовательно, ответ равен \(1\).
Во втором наборе входных данных \(a\) уже состоит только из \(0\), поэтому выполнение операций не требуется.
В третьем наборе входных данных Эвирир может изменять \(a\) следующим образом: \([1, \underline{0, 1, 0, 1}] \to [\underline{1, 2}] \to [0]\), так как \(\operatorname{mex}(0, 1, 0, 1) = 2\) и \(\operatorname{mex}(1, 2) = 0\).
В четвертом наборе входных данных Эвирир может выбрать в качестве \(b\) весь массив \(a\), изменив значение \(a\) с \([\underline{3, 1, 4, 1, 5}]\) на \([0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
4
0 1 2 3
6
0 0 0 0 0 0
5
1 0 1 0 1
5
3 1 4 1 5
4
3 2 1 0
7
9 100 0 89 12 2 3
4
0 3 9 0
7
0 7 0 2 0 7 0
1
0
2
0 1
|
1
0
2
1
1
2
1
2
0
1
|