Это сложная версия задачи. Разница между простой и сложной версиями задачи заключается только в ограничении на \(n\). Вы можете делать взломы только в том случае, если обе версии задачи решены.
Дан массив целых чисел \(a\) длины \(n\).
Вы можете выполнять следующую двухшаговую операцию:
- Выбрать индекс \(i\) такой, что \(1 \le i < |a|\) и \(a_i = i\).
- Удалить \(a_i\) и \(a_{i+1}\) из массива и соединить оставшиеся части.
Найдите максимальное количество раз, которое можно применить данную операцию.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество раз, которое можно применить операцию из условия.
Примечание
В первом наборе входных данных одна из возможных оптимальных последовательностей применения операций такая: \([ 1, 5, \color{red}{3}, \color{red}{2}, 4 ] \rightarrow [\color{red}{1}, \color{red}{5}, 4] \rightarrow [4]\).
В третьем наборе входных данных, одна из возможных оптимальных последовательностей применения операций такая: \([1, \color{red}{2}, \color{red}{3}] \rightarrow [1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
1 5 3 2 4
8
2 1 3 4 5 6 7 8
3
1 2 3
4
1 2 4 4
5
4 4 1 3 5
1
1
|
2
3
1
2
0
0
|