
ZOJ Problem Set  3633
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 j in 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 . InputThere 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^311. 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. OutputFor 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. Sample Input5 1 2 3 1 2 3 1 4 1 5 3 5 6 1 2 3 3 2 1 4 1 4 2 5 3 6 4 6 Sample Output1 2 OK 3 3 3 OK HintAlice will check each interval from right to left, don't make mistakes. Author: CHEN, Henghong Contest: ZOJ Monthly, August 2012 