Background

Original problem link: https://oier.team/problems/J3C.

Problem Description

You have a sequence $a$, where each of $1 \sim n$ appears exactly once.

When you choose any pair $1 \le l \le r \le n$ and write $a_l, a_{l+1}, \ldots, a_r$ in a row, you obtain a substring of $a$, denoted as $a_{l\sim r}$. Here, $l$ is called the left endpoint and $r$ is called the right endpoint.

You need to sort all substrings of $a$ in lexicographical order from small to large. However, to avoid an excessively large output, I will give $q$ queries. In each query, a $k$ is given, and you need to find the left and right endpoints of the $k$-th smallest substring in lexicographical order.

If you do not know what lexicographical order is, see here:

For two sequences $p, q$, we say $p$ is lexicographically smaller than $q$ (denoted $p < q$) if and only if there exists a natural number $k$ such that the first $k$ numbers of $p$ and $q$ are the same, and $p_{k+1} < q_{k+1}$.

In particular, if $p$ is a prefix of $q$ and $p \ne q$, then $p$ is also considered lexicographically smaller than $q$.

For example:

• $[1,2] < [3,2]$ (when $k = 0$).
• $[3,1,100] < [3,2,1]$ (when $k = 1$).
• $[3,4] < [3,4,6]$ ($p$ is a prefix of $q$).

Input Format

The first line contains two positive integers $n, q$, representing the length of the sequence and the number of queries.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$, representing the sequence.

Then follow $q$ lines, each containing one positive integer $k$, representing the required rank of the substring.

Output Format

For each query, output one line with two integers $l, r$, indicating that the $k$-th smallest substring in lexicographical order is $a_{l\sim r}$.

3 6
3 1 2
1
2
3
4
5
6

2 2
2 3
3 3
1 1
1 2
1 3

50 25
42 22 27 8 44 11 14 31 37 10 48 15 12 40 13 4 25 9 19 5 2 18 6 1 32 3 38 33 43 34 46 47 23 35 21 20 45 39 50 7 36 17 24 29 16 30 49 26 28 41
1178
991
755
1094
689
132
671
635
421
659
448
334
327
213
1206
453
1160
583
388
781
150
692
23
1162
62

37 48
27 44
3 28
1 46
43 47
20 34
33 37
2 19
15 44
2 43
7 27
6 31
6 24
4 29
32 37
7 32
5 44
19 47
13 47
44 45
23 24
43 50
24 46
5 46
26 30

Hint

[Sample Explanation #1]

The sequence $3,1,2$ has $6$ substrings in total. After sorting from small to large, the result is: $[1], [1,2], [2], [3], [3,1], [3,1,2]$.

[Constraints]

For all testdata, it is guaranteed that $1 \le n, q \le 3\times 10^5$, $1 \le k \le \dfrac{n(n+1)}{2}$, each of $1 \sim n$ appears exactly once in $a_i$, and all inputs are integers.

Translated by ChatGPT 5