TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1345
  • Problem
  • P1345天才的记忆
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    从前有个人,他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题,如果谁能轻松回答出这个问题,便可以继承他的宝藏。题目是这样的:给你一大串数字(编号为1到N,大小可不一定哦!),在你看过一遍之后,它便消失在你面前,随后问题就出现了,给你M个询问,每次询问就给你两个数字A,B,要求你瞬间就说出属于A到B这段区间内的最大数。你能否轻松解决这个问题?

    Input Format

    第一行一个整数N表示数字的个数
    接下来一行为N个数(<=2^31)
    第三行读入一个M,表示你看完那串数后需要被提问的次数
    接下来M行,每行都有两个整数A,B。

    Output Format

    输出共M行,每行输出一个数。

    Sample Input

    6
    34 1 8 123 3 2
    4
    1 2
    1 5
    3 4
    2 3

    Sample Output

    34
    123
    123
    8

    Hint

    对于30%的数据,1<=N<=10000,1<=M<=100
    对于100%的数据,1<=N<=200000,1<=M<=100000.