#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Given a sequence of

**N**numbers**a**,_{1}**a**, ...,_{2}**a**, and a number of d-queries. A d-query is a pair (_{N}**i**,**j**) (1 ≤**i**≤**j**≤**N**). For each d-query (**i**,**j**), you have to return the number of distinct elements in the subsequence**a**,_{i}**a**, ...,_{i + 1}**a**._{j}### Input

- Line 1:
**N**(1 ≤**N**≤ 200000). - Line 2:
**N**numbers**a**,_{1}**a**, ...,_{2}**a**(1 ≤_{N}**a**≤ 10_{i}^{6}). - Line 3:
**Q**(1 ≤**Q**≤ 200000). - In the next
**Q**lines, each line contains 2 numbers,**i**,**j**representing a d-query (1 ≤**i**≤**j**≤**N**).

### Output

- For each d-query (
**i**,**j**), print the number of distinct elements in the subsequence**a**,_{i}**a**, ...,_{i + 1}**a**in a single line._{j}

### Sample Input 1

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

### Sample Output 1

```
3
2
3
```

### Sample Input 2

```
10
8 1 4 3 10 1 7 4 8 1
5
1 1
3 4
2 9
2 2
4 10
```

### Sample Output 2

```
1
2
6
1
6
```

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 20 | 1s | 256MB | Minimum |

2 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o dquery -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512