Единственная разница между двумя версиями состоит в том, что в этой версии \(n \leq 2 \cdot 10^5\) и сумма по \(n\) по всем наборам входных данных теста не превосходит \(2 \cdot 10^5\).
Терминал — это ряд из \(n\) равных отрезков, пронумерованных от \(1\) до \(n\) по порядку. Есть два терминала, один над другим.
Вам дан массив \(a\) длины \(n\). Для всех \(i = 1, 2, \dots, n\) должен быть прямой провод из некоторой точки на отрезке \(i\) верхнего терминала в некоторую точку на отрезке \(a_i\) нижнего терминала. Например, на следующих рисунках показаны два возможных соединения, при \(n=7\) и \(a=[4,1,4,6,7,7,5]\).
Пересечение происходит, когда два провода имеют общую точку. На картинке выше пересечения обведены красным.
Какое максимальное количество пересечений может быть при оптимальном размещении проводов?
Примечание
Первый пример показан на втором рисунке в условии.
Во втором примере при единственно возможном соединении появляется пересечение двух проводов, поэтому ответ равен \(1\).
В третьем тестовом примере единственно возможное соединение состоит из одного провода, поэтому ответ равен \(0\).