Codeforces Round 960 (Div. 2) |
---|
Закончено |
У вас есть массив $$$a$$$ размера $$$n$$$.
Отрезок $$$[l, r](1 \le l < r \le n)$$$ называется многоугольным отрезком в том случае, если выполняются следующие условия:
Обработайте $$$q$$$ запросов двух типов:
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Для каждого набора входных данных:
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, а сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого запроса, если подходящего отрезка нет, выведите в отдельной строке $$$-1$$$. В противном случае выведите длину самого длинного отрезка, удовлетворяющего вышеприведенному условию.
25 63 1 2 2 81 1 31 1 41 1 52 1 51 1 41 1 54 10500000000000 500000000000 1000000000000 5000000000001 1 31 2 41 1 42 1 4999999999992 3 9999999999991 1 31 2 41 1 42 3 10000000000001 1 3
-1 4 4 3 5 -1 -1 4 -1 3 4 -1
В первом запросе первого набора входных данных не существует многоугольного отрезка. Например, если взять отрезок $$$[1,3]$$$, нельзя сделать треугольник со сторонами $$$a_1=3$$$, $$$a_2=1$$$ и $$$a_3=2$$$.
Во втором запросе первого набора входных данных самый длинный многоугольный отрезок — $$$[1,4]$$$. Вы можете сделать четырехугольник со сторонами $$$a_1=3$$$, $$$a_2=1$$$, $$$a_3=2$$$ и $$$a_4=2$$$.
Название |
---|