Вам задан массив \(a_1, a_2, \dots, a_n\). Вы можете выполнять на нем следующую операцию произвольное количество раз:
После каждой такой операции длина массива уменьшается на один (и элементы перенумеровываются соответствующим образом). Массив \(a\) какой минимальной длины вы можете получить?
В первой строке задано одно целое число \(n\) (\(1 \le n \le 500\)) — первоначальная длина массива \(a\).
Во второй строке заданы \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 1000\)) — первоначальный массив \(a\).
Выведите единственное число — минимально возможную длину массива, которую можно получить после применения операции, описанной выше, произвольное количество раз.
В первом примере, одна из оптимальных последовательностей операций такая: \(4\) \(3\) \(2\) \(2\) \(3\) \(\rightarrow\) \(4\) \(3\) \(3\) \(3\) \(\rightarrow\) \(4\) \(4\) \(3\) \(\rightarrow\) \(5\) \(3\).
Во втором примере, одна из оптимальных последовательностей операций такая: \(3\) \(3\) \(4\) \(4\) \(4\) \(3\) \(3\) \(\rightarrow\) \(4\) \(4\) \(4\) \(4\) \(3\) \(3\) \(\rightarrow\) \(4\) \(4\) \(4\) \(4\) \(4\) \(\rightarrow\) \(5\) \(4\) \(4\) \(4\) \(\rightarrow\) \(5\) \(5\) \(4\) \(\rightarrow\) \(6\) \(4\).
В третьем и четвертом примере, не возможно применить операцию ни разу.
5 4 3 2 2 3
2
7 3 3 4 4 4 3 3
3 1 3 5
3
1 1000
1
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач