U80510 甜蜜蜜的Seaway

不忍看到女朋友在矩阵里迷失，FSW最后还是乖乖出来认罚qwq。为了挽回女朋友受伤的心灵，他准备给女朋友讲以前的甜蜜故事...

FSW和女朋友情感发展的历程一共发生了N个事件（编号为1到N），每个事件都有一个甜蜜值W_i。并且，喜欢回忆的FSW把所有事件分成了K个阶段，每个阶段有一个起始事件和终止事件（用编号表示），现在，他想在每个阶段里都挑一个故事来讲，为了让女朋友尽快原谅他，他当然要挑每个阶段甜蜜值最大的那个事件，请你帮他回忆一下，在每个阶段里FSW和女朋友发生的所有故事中，最甜蜜的事件的甜蜜值是多少。

输入文件的第一行只有一个整数N，接下来的一行，有N个整数，表示第i个事件的甜蜜值W_i。接下来的一行是一个整数K，代表FSW把所有事件分成了K个阶段。接下来的K行，每行两个整数，表示第i个阶段的起始事件和终止事件的编号。

输出文件有K行，第i行表示在第i个阶段里最大的甜蜜值。

数据范围：1< =N< =200000，1< =K< =10000，1