C. Побег Нео
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нео хочет сбежать из Матрицы. Перед ним находится $$$n$$$ кнопок, выстроенных в ряд. Каждая кнопка имеет вес, заданный целым числом: $$$a_1, a_2, \ldots, a_n$$$.

Нео обездвижен, однако он может создавать и перемещать клонов. То есть он может совершать сколько угодно действий следующих двух видов в любом порядке:

  1. Создать клона перед одной конкретной кнопкой.
  2. Переместить существующего клона на одну позицию влево или вправо.

Как только клон оказывается перед какой-то ещё не нажатой кнопкой — не важно, при создании или перемещении — он сразу же нажимает её. Если же кнопка уже нажата, клон ничего не делает — кнопки могут быть нажаты только один раз.

Для побега Нео необходимо нажать все кнопки в таком порядке, чтобы последовательность их весов была невозрастающей — то есть, если $$$b_1, b_2, \ldots, b_n$$$ — веса кнопок в порядке нажатия, то должно выполняться $$$b_1 \geq b_2 \geq \cdots \geq b_n$$$.

Ваша задача — определить минимальное количество клонов, которое необходимо создать Нео для того, чтобы нажать все кнопки в допустимом порядке.

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

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

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

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

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

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

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

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

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

  1. Создать клона перед пятой кнопкой (с весом $$$5$$$).
  2. Создать клона перед первой кнопкой (с весом $$$4$$$).
  3. Переместить второго клона с первой кнопки на вторую (с весом $$$3$$$).
  4. Переместить второго клона со второй кнопки на третью (с весом $$$2$$$).
  5. Переместить первого клона с пятой кнопки на четвёртую (с весом $$$1$$$).
Таким образом, последовательность нажатия кнопок будет $$$5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$, что соответствует требованию. Можно показать, что количество созданных клонов является наименьшим возможным.

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

  1. Создать клона перед второй кнопкой (с весом $$$1$$$).
  2. Переместить клона со второй кнопки на третью (с весом $$$1$$$).
  3. Переместить клона с третьей кнопки на вторую (уже нажата).
  4. Переместить клона со второй кнопки на первую (с весом $$$1$$$).
Таким образом, последовательность нажатия кнопок будет $$$1 \rightarrow 1 \rightarrow 1$$$.