Codeforces Round 656 (Div. 3) |
---|
Закончено |
Вам задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Вам нужно найти длину наименьшего (кратчайшего) префикса элементов, которые вам нужно удалить из $$$a$$$, чтобы сделать его хорошим массивом. Напомним, что префиксом массива $$$a=[a_1, a_2, \dots, a_n]$$$ называется подмассив, состоящий из первых нескольких элементов: префикс массива $$$a$$$ длины $$$k$$$ — это массив $$$[a_1, a_2, \dots, a_k]$$$ ($$$0 \le k \le n$$$).
Массив $$$b$$$ длины $$$m$$$ называется хорошим, если вы можете получить из него неубывающий массив $$$c$$$ ($$$c_1 \le c_2 \le \dots \le c_{m}$$$), повторяя следующую операцию $$$m$$$ раз (изначально массив $$$c$$$ пустой):
Например, если делаем $$$4$$$ операции: возьмем $$$b_1$$$, затем $$$b_{m}$$$, затем $$$b_{m-1}$$$ и в конце $$$b_2$$$, то $$$b$$$ становится $$$[b_3, b_4, \dots, b_{m-3}]$$$ и $$$c =[b_1, b_{m}, b_{m-1}, b_2]$$$.
Рассмотрим следующий пример: $$$b = [1, 2, 3, 4, 4, 2, 1]$$$. Этот массив хороший, потому что мы можем получить неубывающий массив $$$c$$$ из него с помощью следующей последовательности операций:
Заметьте, что массив, состоящий из одного элемента считается хорошим.
Выведите длину кратчайшего префикса $$$a$$$, который необходимо удалить для того, чтобы сделать $$$a$$$ хорошим массивом. Заметьте, что необходимая длина может быть равна $$$0$$$.
Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.
Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.
Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину $$$a$$$. Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), где $$$a_i$$$ — $$$i$$$-й элемент в $$$a$$$.
Гарантируется, что сумма всех $$$n$$$ не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).
Для каждого набора тестовых данных выведите ответ на него: длину кратчайшего префикса элементов, которые нужно удалить из $$$a$$$, чтобы он стал хорошим массивом.
5 4 1 2 3 4 7 4 3 3 8 4 5 2 3 1 1 1 7 1 3 1 4 5 3 2 5 5 4 3 2 3
0 4 0 2 3
В первом наборе тестовых данных примера массив $$$a$$$ уже является хорошим, поэтому нам нет необходимости удалять какой-либо префикс.
Во втором наборе тестовых данных примера изначальный массив $$$a$$$ не является хорошим. Давайте удалим первые $$$4$$$ элемента $$$a$$$, результат будет равен $$$[4, 5, 2]$$$. Получившийся массив является хорошим. Вы можете доказать, что если удалить меньшее количество первых элементов, результат не будет хорошим.
Название |
---|