As a doll master, Alice owns a wide range of dolls, and each of them has a number tip on it‘s back, the tip can be treated as a positive integer. (the number can be repeated). One day, Alice hears that her best friend Marisa‘s birthday is coming , so she decides to sent Marisa some dolls for present. Alice puts her dolls in a row and marks them from 1 to n. Each time Alice chooses an interval from i to jin the sequence ( include i and j ) , and then checks the number tips on dolls in the interval from right to left. If any number appears more than once , Alice will treat this interval as unsuitable. Otherwise, this interval will be treated as suitable.

This work is so boring and it will waste Alice a lot of time. So Alice asks you for help .

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 integeru, v ( 1≤ u< v≤ n ),indicate the left endpoint and right endpoint of the interval. Process to the end of input.

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.

Print an blank line after each case.

51 2 3 1 231 41 53 561 2 3 3 2 141 42 53 64 6

12OK333OK

Hint

Alice will check each interval from right to left, don‘t make mistakes.

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<cstdlib>#include<algorithm>#include<map>using namespace std;map<int,int> mp;#define N 500010int n,num[N],m;int main(){      int x,y;      while(scanf("%d",&n)!=EOF)      {            int pos;            for(int i=1;i<=n;i++)                  scanf("%d",&num[i]);            scanf("%d",&m);            while(m--)            {                 bool flag=false;                 mp.clear();                 scanf("%d%d",&x,&y);                 for(int i=y;i>=x;i--)                 {                       if(!mp.count(num[i]))                       {                             mp[num[i]]=1;                       }                       else                       {                             pos=i;                             flag=true;                             break;                       }                 }                 if(!flag)                 {                       printf("OK\n");                 }                 else                 {                       printf("%d\n",num[pos]);                 }            }            printf("\n");      }      return 0;}