Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: minimumas.in

Rezultatų failas: minimumas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Minimumas

Jums duotas sąrašas skaičių a_1,a_2,...,a_n bei q užklausų. Kiekvieną užklausą sudaro du sveikieji skaičiai L_i bei R_i. Jūsų užduotis - kiekvienai tokiai užklausai surasti reikšmę max(a_{L_i},a_{L_{i+1}},...,a_{R_i}).

Pradiniai duomenys

Pirmoje eilutėje pateiktas vienas sveikasis skaičius n (1\\leqn\\leq2\\cdotp10^5).

Antroje eilutėje pateikta n tarpais atskirtų sveikųjų skaičių a_1,...,a_n (1\\leqa_i\\leq10^9).

Trečioje eilutėje pateiktas vienas sveikasis skaičius q (1\\leqq\\leq2\\cdotp10^5).

Toliau seka q eilučių. i-ojoje iš jų yra du sveikieji skaičiai L_i ir R_i (1\\leqL_i\\leqR_i\\leqN).

Rezultatai

Jūsų programa turi išvesti q sveikųjų skaičių, po vieną eilutėje. i-asis iš šių skaičių turi būti atsakymas į i-ąją užklausą.

Pastaba. Uždavinys reikalauja didelio išvesties kiekio, tad nepamirškite naudoti greitų išvesties/įvesties operacijų.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
1 4 1
3
2 2
2 3
1 1
 
4
4
1