Maksimum

Giriş

Birinci sətirdə massivdəki elementlərin sayı olan tam ədəd n~(1 \le n \le 10^5) verilir.

İkinci sətirdə massivin elementləri olan $n$ tam ədəd a_1, a_2, \ldots, a_n~(-10^9 \le a_i \le 10^9) verilir.

Üçüncü sətirdə sorğuların sayı olan tam ədəd q~(1 \le q \le 5 \cdot 10^5) verilir.

Sonrakı $q$ sətirin hər birində aralığın uc nöqtələrini təmsil edən iki müsbət tam ədəd $l$ və r~(1 \le l, r \le n) verilir. Hər sorğu üçün $l$-dən $r$-ə qədər (hər ikisi daxil olmaqla) olan alt massivdə maksimum dəyəri tapmalısınız.

Çıxış

Hər sorğu üçün müvafiq aralıqdakı maksimum dəyəri çap edin.

Nümunələr