Sequence and Queries 6

For each query range [i, j], report the highest number of occurrences of any single value inside that range.

Hard9Segment treeDivide and conquerBinary searchPrefix sumNo attempts yetTime limit2sMemory limit512 MB

Description

Examples2

You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$ . Write a program that processes the following query on this sequence.

i j: print how many times the most frequent value among $A_i, A_{i+1}, \ldots, A_j$ occurs.

The first line contains the length of the sequence $N$ ( $1 \le N \le 100\,000$ ).

The second line contains $A_1, A_2, \ldots, A_N$ separated by spaces. ( $1 \le A_i \le 100\,000$ )

The third line contains the number of queries $M$ ( $1 \le M \le 100\,000$ ).

Each of the next $M$ lines contains one query $i$ , $j$ . ( $1 \le i \le j \le N$ )

Print the answer to each query on its own line, in the order the queries are given.