Назовём последовательность чисел \(a_1, a_2, \ldots, a_n\) магической, если для всех \(1 \leq i \leq n-1\) верно, что: \(\operatorname{min}(a_1, \ldots, a_i) \geq \operatorname{mex}(a_{i+1}, \ldots, a_n)\). В частности, любая последовательность длины \(1\) является магической.
Наименьшее исключенное (MEX) набора чисел \(a_1, a_2, \ldots, a_k\) определяется как наименьшее неотрицательное целое число \(t\), которое не встречается в наборе чисел \(a\).
Вам дана последовательность \(a\) из \(n\) целых неотрицательных чисел. Найдите максимально возможную длину магической подпоследовательности\(^{\text{∗}}\) последовательности \(a\).
Выходные данные
Для каждого набора входных данных выведите одно число — максимально возможную длину магической подпоследовательности последовательности \(a\).
Примечание
В первом наборе входных данных сама последовательность \([4, 3, 2, 1, 0]\) является магической, так как:
- \(\operatorname{min}(4) = 4, \operatorname{mex}(3, 2, 1, 0) = 4\). \(4 \geq 4\)
- \(\operatorname{min}(4, 3) = 3, \operatorname{mex}(2, 1, 0) = 3\). \(3 \geq 3\)
- \(\operatorname{min}(4, 3, 2) = 2, \operatorname{mex}(1, 0) = 2\). \(2 \geq 2\)
- \(\operatorname{min}(4, 3, 2, 1) = 1, \operatorname{mex}(0) = 1\). \(1 \geq 1\)
Во втором наборе входных данных последовательность \([4, 3, 3, 2, 1, 0]\) не является магической, так как \(\operatorname{min}(4, 3) = 3, \operatorname{mex}(3, 2, 1, 0) = 4\), \(3 < 4\). Но подпоследовательность \([4, 3, 2, 1, 0]\) этой последовательности является магической, поэтому ответ \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
5
4 3 2 1 0
6
4 3 3 2 1 0
4
2 0 1 2
1
777
4
1000000000 1 7 9
2
0 1
2
1 2
4
0 1 0 1
|
5
5
3
1
4
2
2
3
|