Egors_Gaming_Addiction — OOI qualification
Task type: batch | Time limit: 2 s | Memory limit: 512 MB | Difficulty: 25
Algorithms: line sweep, range queries, segment tree, offline queries

# Egor's Gaming Addiction

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 2 seconds       |
| Memory limit: | 512 megabytes   |

The boy Egor constantly plays the trendy game "TOTA" which features $n$ types of heroes. A line of heroes of length $k$ is defined as a sequence of heroes with types $b_1, b_2, ..., b_k$. Egor calls a line of heroes of length $k$ terrible if each hero type from 1 to $k$ appears in this line exactly once. In other words, a line of length $k$ is terrible for Egor if for every $1 \le i \le k$, there exists a position $j$ in the line such that $b_j = i$.

Egor has a gaming addiction, so every day he plays the game with his friend Timofey. Since the game is still under development, each day the same sequence of heroes of length $n$ is available for constructing lines, where the $i$-th hero has type $a_i$. Timofey will play with Egor for $q$ days. Each day, a certain number $l_i$ is fixed - the index of the first hero to be taken in the line. Accordingly, on the $i$-th day, Timofey can assemble a line of heroes against Egor with indices $a_{l_i}, a_{l_i+1}, ... a_{r_i}$ for any $r_i$ such that $l_i \le r_i \le n$.

Timofey really wants Egor to stop playing "TOTA" all the time and instead focus on studying. To do this, Timofey wants to deprive Egor of all the joy of playing. Each day, Egor has $x_i$ joy, which Timofey wants to take away by setting a terrible line against him. It is known that Egor's joy will be taken away if the length of the terrible line is at least the amount of joy, meaning that on day $i$, Egor will lose all his joy if a line of length at least $x_i$ is set against him.

Timofey wants to deprive Egor of joy as often as possible, so for each $i$ from 1 to $q$, he wants to know the minimum length of the line that will deprive Egor of joy on day $i$, as well as the number of possible line configurations on day $i$ that will take away Egor's joy. Unfortunately, due to frequent playing of "TOTA" Timofey's cognitive abilities have diminished, and he will need your help to solve this problem.

## Input

The first line contains a single integer $g$ ($0 \le g \le 8$) - the group number for this test.

The second line contains two integers $n$ and $q$ ($1 \le n, q \le 10^6$) - the number of heroes and the number of days, respectively.

The third line contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \le a_i \le n$) - the types of heroes in the initial list.

In each of the following $q$ lines, there are two integers $l_i$ and $x_i$ ($1 \le l_i \le n$, $1 \le x_i \le n - l_i + 1$) - the index of the first hero in the line on day $i$ and the amount of joy Egor has on day $i$.

## Output

Output $q$ lines, in the $i$-th line output the answer for day $i$ - the minimum length of the terrible line and the number of terrible lines that will deprive Egor of joy on day $i$. If no lines on day $i$ will deprive Egor of joy, output -1 0.

## Examples

| standard input | standard output |
|----------------|-----------------|
| 0              | 1 2             |
| 6 3            | 4 1             |
| 1 4 2 3 1 4    | 3 2             |
| 1 1            |                 |
| 2 1            |                 |
| 3 1            |                 |
| 0              | -1 0            |
| 3 1            |                 |
| 3 3 1          |                 |
| 1 1            |                 |

## Note

Consider the first example.

On the first day, Egor has a joy level of $x_1 = 1$, so to deprive him of joy, a terrible line of at least length 1 is required, but starting from hero $l_1 = 1$, there are two terrible lines:

- 1
- 1, 4, 2, 3

The minimum length of a terrible line is 1, and their count is two.

On the second day, there is a new number $l_2 = 2$, for which there is only one terrible line: 4, 2, 3, 1. Note that the line 4, 2, 3, 1, 4 is not terrible because hero type 4 appears twice in it.

On the third day, lines are formed starting from hero number $l_3 = 3$, and on this day, there are two terrible lines:

- 2, 3, 1
- 2, 3, 1, 4

## Scoring

The tests for this problem consist of eight groups. Points for each group are awarded only if all tests of the group and all tests of some of the previous groups are passed. Note that passing the samples is not required for some groups. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

| Group | Points | Additional constraints |   | Required groups | Comment                                         |
|-------|--------|------------------------|---|-----------------|-------------------------------------------------|
|       |        | $n$                    | $q$ |                 |                                                 |
| 0     | 0      | -                      | - | -               | Samples.                                        |
| 1     | 8      | $n \le 1000$           | $q \le 1000$  | 0               |                                                 |
| 2     | 7      | $n \le 5000$           | $q \le 5000$  | 0, 1            |                                                 |
| 3     | 9      | $n \le 200000$         | $q \le 200000$ | -               | $a_i = (i - 1) \mod x + 1$ for a fixed $x > 0$  |
| 4     | 12     | $n \le 200000$         | $q \le 200000$ | -               | $a$ is a permutation of numbers from 1 to $n$   |
| 5     | 19     | $n \le 200000$         | $q \le 200000$ | -               | $x_i = 1$ for all queries                       |
| 6     | 10     | $n \le 200000$         | $q \le 200000$ | 0 - 5           |                                                 |
| 7     | 14     | $n \le 500000$         | $q \le 500000$ | 0 - 6           |                                                 |
| 8     | 21     | -                      | - | 0 - 7           | Offline-testing.                                |

Starter code: