11201120 SUSTech Online Judge
Problem 1120 --Skipping inquiry

## 1120: Skipping inquiry

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 224  Solved: 42
[Submit][Status][Web Board]

## Description

Grace has n numbers. They are a1……a. Let M = sqrt(n), meaning the biggest integer which is less than or equal to the square root of n. And there are n queries. For each query, there are two integers x and y. You need to answer the M-th biggest number among ax, ax+y……(x + ky <= n) . If the number of the elements is less than M, please output -1.

## Input

The first line will be an integer T, which is the number of test cases. (1 <= T <= 5). For each test case, the first line will be an integer n (1 <= n <= 40000). The second line will be n integers which are a1……an(1 <= ai <= 109). For the following n lines, each line contains two integers x and y

## Output

For each test output the M-th biggest element or -1 in one line.

## Sample Input

1
5
1 2 3 4 5
1 1
2 2
3 3
4 4
5 5

## Sample Output

4
2
-1
-1
-1

[Submit][Status]