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

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел.

Пока массив не опустеет, над ним проводится операция, состоящая из двух шагов:

  • сначала находится максимальный элемент в массиве (если максимальных элементов несколько, выбирается последний из них);
  • потом все элементы после найденного элемента, включая его, удаляются из массива.

Ваша задача — определить, сколько операций будет выполнено перед тем, как массив опустеет.

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

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

Каждый набор входных данных состоит из двух строк:

  • в первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$);
  • во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Дополнительные ограничения на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно целое число — количество операций, которые будут выполнены.

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

В первом примере массив равен $$$[2, 1, 2, 3, 1]$$$. На нем выполняются следующие операции:

  • сначала выбирается $$$4$$$-й элемент. Удаляются последние два элемента, и массив становится $$$[2, 1, 2]$$$;
  • затем выбирается $$$3$$$-й элемент. Он удаляется, и массив становится $$$[2, 1]$$$;
  • затем выбирается $$$1$$$-й элемент. Два оставшихся элемента удаляются, и массив становится пустым после $$$3$$$ операций.