D. Симон и борьба с пиками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

My loveliest wishes dissolved into the air; At eighteen, I poured my dreams into the mic to share.
— SHUN, 720

Мы называем массив $$$b$$$ длины $$$m$$$ классным, если и только если:

  • Не существует ни одного индекса $$$i$$$ ($$$1 \lt i \lt m$$$) такого, что $$$b_i=\max(\{b_{i-1}, b_i, b_{i+1}\})$$$.

У Симона есть массив $$$a$$$ размером $$$n$$$. Изначально массив является перестановкой$$$^{\text{∗}}$$$.

Он должен выполнять следующую операцию, пока массив не станет классным:

  • Выбрать индекс $$$i$$$ ($$$1 \lt i \lt n$$$) такой, что $$$a_i=\max(\{a_{i-1}, a_i, a_{i+1}\})$$$.
  • Затем он может удалить $$$a_{i-1}$$$ или $$$a_{i+1}$$$ из массива. После удаления в массиве появляется разрыв, и левая и правая стороны разрыва будут соединены.

Найдите минимальное количество операций, которые должен выполнить Симон.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5\cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит целое число $$$n$$$ ($$$3\le n\le 5\cdot 10^5$$$) — размер массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$, все $$$a_i$$$ различны) — массив, который изначально есть у Симона.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot 10^5$$$.

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

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

Пример
Входные данные
5
3
1 2 3
5
4 1 3 2 5
6
4 5 3 6 2 1
7
6 5 1 7 4 2 3
15
7 4 10 12 9 14 5 3 8 11 1 15 2 13 6
Выходные данные
0
1
3
3
9
Примечание

В первом наборе входных данных массив изначально классный, поэтому Симон не может выполнить никаких операций. Ответ равен $$$0$$$.

Во втором наборе входных данных Симон может выполнить следующее:

  • Выбрать индекс $$$3$$$, потому что $$$a_3=\max(\{a_2,a_3,a_4\})$$$. Затем он удаляет $$$a_{2}$$$ из массива. Массив становится $$$[4,3,2,5]$$$.

Мы видим, что массив теперь классный. Таким образом, ответ равен $$$1$$$.

В третьем наборе входных данных Симон может выполнить следующее:

  • Выбрать индекс $$$2$$$ и удалить $$$a_1$$$ из массива. Массив становится $$$[5,3,6,2,1]$$$.
  • Выбрать индекс $$$3$$$ и удалить $$$a_2$$$ из массива. Массив становится $$$[5,6,2,1]$$$.
  • Выбрать индекс $$$2$$$ и удалить $$$a_1$$$ из массива. Массив становится $$$[6,2,1]$$$.

Таким образом, Симон сделает массив классным за $$$3$$$ операции.