H2. Максимизация пересечений (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственная разница между двумя версиями состоит в том, что в этой версии $$$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]$$$.

Пересечение происходит, когда два провода имеют общую точку. На картинке выше пересечения обведены красным.

Какое максимальное количество пересечений может быть при оптимальном размещении проводов?

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина массива.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — элементы массива.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора выведите единственное целое число — максимальное количество пересечений, при оптимальном расположении проводов.

Пример
Входные данные
4
7
4 1 4 6 7 7 5
2
2 1
1
1
3
2 2 2
Выходные данные
6
1
0
3
Примечание

Первый пример показан на втором рисунке в условии.

Во втором примере при единственно возможном соединении появляется пересечение двух проводов, поэтому ответ равен $$$1$$$.

В третьем тестовом примере единственно возможное соединение состоит из одного провода, поэтому ответ равен $$$0$$$.