Олимпиадный тренинг

Задача . B. Выворачивание массива

Задача

Вам дан массив \(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\) — наименьшее количество выворачиваний, после которых массив не будет меняться.

Примечание

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

Первое выворачивание: \(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\).

Примеры

№	Входные данные	Выходные данные
1	3 5 2 4 1 5 3 5 5 3 2 4 1 4 1 1 1 1	1 2 0

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	2

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет