#P1982. Alice'spresent

Alice'spresent

As a doll master, Alice owns a wide range of dolls, and each ofthem has a number tip on it's back, the tip can be treated as a positiveinteger. (the number can be repeated). One day, Alice hears that her bestfriend Marisa's birthday is coming , so she decides to sent Marisa some dollsfor present. Alice puts her dolls in a row and marks them from 1 to n. Each time Alice choosesan interval from i to j in the sequence ( include i and j ) , and then checks the number tips ondolls in the interval from right to left. If any number appears more than once, Alice will treat this interval as unsuitable. Otherwise, this interval willbe treated as suitable.<o:p></o:p>

This work is so boring and it will waste Alice a lot of time. SoAlice asks you for help .<o:p></o:p>

Input

There are multiple test cases. For each test case:
The first line contains an integer n ( 3≤ n ≤ 500,000) ,indicate the number of dolls which Alice owns.
The second line contains n positive integers , decribe the number tips on dolls. All of them are less than 2^31-1. The third line contains an interger m ( 1 ≤ m ≤ 50,000 ),indicate how many intervals Alice will query. Then followed by m lines, each line contains two integer u, v ( 1≤ u< v≤ n ),indicate the left endpoint and right endpoint of the interval. Process to the end of input.

Output

For each test case:
For each query, If this interval is suitable , print one line "OK". Otherwise, print one line ,the integer which appears more than once first.

(Hint :Alice will check each interval from right to left, don't make mistakes.)

Sample Input

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

Sample Output

</p> 
1
2
OK

HINT

Source

NYOJ

统计

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 主题
  4. Worker 0 in 10ms
  5. Powered by Hydro v4.11.2 Community