原題來(lái)自：Vijos P1512

從前有個(gè)人名叫 W and N and B，他有著天才般的記憶力，他珍藏了許多許多的寶藏。在他離世之后留給后人一個(gè)難題（專門考驗(yàn)記憶力的?。。绻l(shuí)能輕松回答出這個(gè)問(wèn)題，便可以繼承他的寶藏。

題目是這樣的：給你一大串?dāng)?shù)字（編號(hào)為 1 到 N，大小可不一定哦?。谀憧催^(guò)一遍之后，它便消失在你面前，隨后問(wèn)題就出現(xiàn)了，給你 M 個(gè)詢問(wèn)，每次詢問(wèn)就給你兩個(gè)數(shù)字 A,B，要求你瞬間就說(shuō)出屬于 A 到 B 這段區(qū)間內(nèi)的最大數(shù)。

一天，一位美麗的姐姐從天上飛過(guò)，看到這個(gè)問(wèn)題，感到很有意思（主要是據(jù)說(shuō)那個(gè)寶藏里面藏著一種美容水，喝了可以讓這美麗的姐姐更加迷人），于是她就竭盡全力想解決這個(gè)問(wèn)題。BUT，她每次都以失敗告終，因?yàn)檫@數(shù)字的個(gè)數(shù)是在太多了！于是她請(qǐng)?zhí)觳诺哪銕退鉀Q。如果你幫她解決了這個(gè)問(wèn)題，可是會(huì)得到很多甜頭的哦！

第一行一個(gè)整數(shù) N 表示數(shù)字的個(gè)數(shù)，接下來(lái)一行為 N 個(gè)數(shù)。第三行讀入一個(gè) M，表示你看完那串?dāng)?shù)后需要被提問(wèn)的次數(shù)，接下來(lái) M 行，每行都有兩個(gè)整數(shù) A,B。

輸出共 M 行，每行輸出一個(gè)數(shù)，表示對(duì)一個(gè)問(wèn)題的回答。

數(shù)據(jù)范圍與提示：

對(duì)于 30% 的數(shù)據(jù)，1≤N≤10⁴,1≤M≤100；

對(duì)于 100% 的數(shù)據(jù)，1≤N≤2×10⁵,1≤M≤10⁴ 。

信息學(xué)一本通 數(shù)據(jù)結(jié)構(gòu)