F. И снова задача о сортировке
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$ из $$$n$$$ элементов. Также есть $$$q$$$ изменений массива. Перед первым изменением и далее после каждого изменения вы бы хотели узнать следующее:

Какой подотрезок минимальной длины необходимо отсортировать по неубыванию, чтобы массив $$$a$$$ был полностью отсортирован по неубыванию?

Более формально, вы хотите выбрать подотрезок массива $$$(l, r)$$$ с минимальным значением $$$r - l + 1$$$. После этого вы отсортируете элементы $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$ и хотите, чтобы выполнялось условие $$$a_{i} \le a_{i + 1}$$$ для всех $$$1 \le i < n$$$. Если же массив уже отсортирован по неубыванию, то $$$l$$$ и $$$r$$$ стоит считать равными $$$-1$$$.

Обратите внимание, что нахождение таких $$$(l, r)$$$ никак не меняет массив. А сами изменения имеют вид: присвоить $$$a_{pos} = x$$$ для заданных $$$pos$$$ и $$$x$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_{i}$$$ ($$$0 \le |a_{i}| \le 10^{9}$$$) — изначальные элементы массива $$$a$$$.

В третьей строке каждого набора входных данных дано число $$$q$$$ ($$$0 \le q \le 5 \cdot 10^{5}$$$) — количество изменений массива.

Следующие $$$q$$$ строк каждого набора входных данных содержат по два целых числа $$$pos_{i}$$$ ($$$1 \le pos_{i} \le n$$$) и $$$val_{i}$$$ ($$$0 \le |val_{i}| \le 10^{9}$$$) — это означает, что при $$$i$$$-м изменении $$$a_{pos_{i}}$$$ присваивается значение $$$val_{i}$$$.

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

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

Для каждого набора входных данных выведите $$$q + 1$$$ строку. В каждой строке должно быть по $$$2$$$ целых числа $$$l, r$$$ — границы минимального подотрезка, при сортировке которого массив $$$a$$$ станет полностью отсортирован. Если $$$a$$$ уже отсортирован, то выведите $$$l = -1$$$, $$$r = -1$$$.

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

Рассмотрим первый набор входных данных:

  • Изначально массив отсортирован по неубыванию: $$$[2, 2, 3, 4, 5]$$$
  • После первого запроса массив выглядит так: $$$[\color{red}{2}, \color{red}{1}, 3, 4, 5]$$$.
  • После второго запроса массив выглядит так: $$$[\color{red}{2}, \color{red}{1}, \color{red}{3}, \color{red}{1}, 5]$$$.
  • После третьего запроса массив выглядит так: $$$[1, 1, \color{red}{3}, \color{red}{1}, 5]$$$.

Красным цветом показаны отрезки, которые нужно отсортировать, чтобы весь массив был отсортирован по неубыванию.