У вас есть массив \(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\).
Выходные данные
Для каждого набора входных данных выведите \(q + 1\) строку. В каждой строке должно быть по \(2\) целых числа \(l, r\) — границы минимального подотрезка, при сортировке которого массив \(a\) станет полностью отсортирован. Если \(a\) уже отсортирован, то выведите \(l = -1\), \(r = -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]\).
Красным цветом показаны отрезки, которые нужно отсортировать, чтобы весь массив был отсортирован по неубыванию.
Примеры
| № | Входные данные | Выходные данные |
|
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
|