줄넘기

Interview

Time limit2sMemory limit256 MB

Summary

For each query range [l, r], find the longest segment whose two ends have equal heights and no student in between has that same height, or print 0.

Level: Medium5 of 10
Topics: Hash map, Sorting, Implementation
Solved: No attempts yet

문제

$N$ students stand in a line to jump rope together. The height of student $i$ is $A_i$ . You pick some of these students for a group jump rope. The process goes as follows.

First, you pick students with consecutive numbers to be the group. Suppose you pick students from number $s$ to number $e$ . Students $s$ and $e$ turn the rope, and the students in between jump over it.

If the two students holding the rope have different heights, the rope is hard to turn, so the two holders must have the same height. (That is, $A_s = A_e$ .) Also, if another student in between has the same height, that student gets in the way, so every student in between must have a height different from $A_s$ .

There are $Q$ queries. In the $i$ -th query, only students with numbers from $l_i$ to $r_i$ inclusive may take part in the jump rope. Return the maximum number of students who can take part in the jump rope. If no jump rope is possible, print 0.

입력

The first line contains $N$ , the number of students.

The second line contains the heights $A_1, A_2, \cdots, A_N$ .

The third line contains $Q$ , the number of queries.

Each of the next $Q$ lines contains two integers $l_i$ and $r_i$ .

출력

For each of the $Q$ queries, print the maximum number of students who can take part in the jump rope, one per line. If no jump rope is possible, print 0.

제한

$2 \le N, Q \le 5 \times 10^5$
$1 \le A_i \le 10^9$ ( $1 \le i \le N$ )
$1 \le l_i < r_i \le N$ ( $1 \le i \le Q$ )

Examples1

Example 1
Input
```
6
4 2 2 1 4 1
3
1 6
2 4
3 5
```
Expected output
```
5
2
0
```