Sequence and Queries 4

Time limit4sMemory limit512 MB

Summary
For each query range [l,r], find the maximum distance between two positions in the range that hold the same value.
Level

Medium7 of 10

Topics
Array, Prefix sum, Binary search, Sorting
Solved
No attempts yet

Problem

You are given a sequence A1,A2,…,ANA_1, A_2, \dots, A_N of length NN whose elements are integers between 1 and KK. Write a program that answers the following query.

  • l r: print max⁡{∣x−y∣:l≤x, y≤r, Ax=Ay}\max\{|x - y| : l \le x,\, y \le r,\ A_x = A_y\}.

The pair x=yx = y also satisfies the condition, so the answer is always at least 0.

Input

The first line contains the length of the sequence NN (1≤N≤100 0001 \le N \le 100\,000) and KK (1≤K≤100 0001 \le K \le 100\,000).

The second line contains A1,A2,…,ANA_1, A_2, \dots, A_N. (1≤Ai≤K1 \le A_i \le K)

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

Each of the next MM lines contains one query, given as ll and rr. (1≤l≤r≤N1 \le l \le r \le N)

Output

Print one answer per line for each query, in the order the queries are given.

Examples2

  1. Example 1

    Input
    7 7
4 5 6 6 5 7 4
5
6 6
5 6
3 5
3 7
1 7
    Expected output
    0
0
1
1
6

  2. Example 2

    Input
    8 3
1 2 3 1 2 3 1 2
4
1 8
2 5
4 6
7 7
    Expected output
    6
3
0
0