Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

B. Выворачивание массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$.

Определим операцию выворачивания массива. Положим значение $$$x = a_n$$$. Далее массив $$$a$$$ делится на две части: левую и правую. Левая часть содержит элементы массива $$$a$$$, которые не больше $$$x$$$ ($$$\le x$$$), а правая — элементы массива $$$a$$$, строго большие $$$x$$$ ($$$> x$$$). Относительный порядок элементов в частях остается таким же, как до выворачивания, то есть разделение выполняется стабильно. Затем части склеиваются: слева левая, справа правая.

Например, если $$$a$$$ равен $$$[2, 4, 1, 5, 3]$$$, то выворачивание происходит так: $$$[2, 4, 1, 5, 3] \to [2, 1, 3], [4, 5] \to [2, 1, 3, 4, 5]$$$.

Мы будем применять операцию выворачивания к массиву $$$a$$$ много раз. Можно показать, что после нескольких операций массив $$$a$$$ больше не будет меняться. Выведите наименьшее число $$$k$$$ такое, что после $$$k$$$ выворачиваний массив больше не будет меняться.

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

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

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

Во второй строке набора находятся $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

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

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

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

Рассмотрим первый пример.

  • Первое выворачивание: $$$a = [1, 4, 2, 5, 3]$$$, $$$x = 3$$$. $$$[2, 4, 1, 5, 3] \to [2, 1, 3], [4, 5] \to [2, 1, 3, 4, 5]$$$.
  • Второе и последующие выворачивании: $$$a = [2, 1, 3, 4, 5]$$$, $$$x = 5$$$. $$$[2, 1, 3, 4, 5] \to [2, 1, 3, 4, 5], [] \to [2, 1, 3, 4, 5]$$$. Эти выворачивания не меняют массив, поэтому ответ $$$1$$$.

Рассмотрим второй пример.

  • Первое выворачивание: $$$a = [5, 3, 2, 4, 1]$$$, $$$x = 1$$$. $$$[5, 3, 2, 4, 1] \to [1], [5, 3, 2, 4] \to [1, 5, 3, 2, 4]$$$.
  • Второе выворачивание: $$$a = [1, 5, 3, 2, 4]$$$, $$$x = 4$$$. $$$[1, 5, 3, 2, 4] \to [1, 3, 2, 4], [5] \to [1, 3, 2, 4, 5]$$$.
  • Третье и последующие выворачивании: $$$a = [1, 3, 2, 4, 5]$$$, $$$x = 5$$$. $$$[1, 3, 2, 4, 5] \to [1, 3, 2, 4, 5], [] \to [1, 3, 2, 4, 5]$$$. Эти выворачивания не меняют массив, поэтому ответ $$$2$$$.