Codeforces Round 960 (Div. 2) |
---|
Finished |
You are given an array $$$a$$$ of size $$$n$$$.
A segment $$$[l, r](1 \le l < r \le n)$$$ is called a polygonal segment only if the following conditions hold:
Process $$$q$$$ queries of two types:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
For each test case:
It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$, and the sum of $$$q$$$ over all test cases will not exceed $$$10^5$$$.
For each query, if there is no suitable segment, output $$$-1$$$ in a new line. Otherwise, output the length of the longest segment satisfying the condition above in a new line.
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
In the first query of the first test case, there is no polygonal segment under the given condition. For example, considering segment $$$[1,3]$$$, you can not form a triangle with side lengths of $$$a_1=3$$$, $$$a_2=1$$$, and $$$a_3=2$$$.
In the second query of the first test case, the longest polygonal segment is $$$[1,4]$$$. You can form a quadrilateral with side lengths of $$$a_1=3$$$, $$$a_2=1$$$, $$$a_3=2$$$, and $$$a_4=2$$$.
Name |
---|