Sizin vəzifəniz çox sadədir: siz yalnız verilmiş parçada maksimumu tapmalısınız. \InputFile İlk sətirdə massivin elementlərinin $n~(1 \le n \le 10^5)$ sayı verilir. Növbəti sətirdə cari massivin $n$ sayda elementləri verilir --- $a_1, a_2, ..., a_n~(-10^9 \le a_i \le 10^9)$. Növbəti sətirdə sorğuların $q~(1 \le q \le 5 \cdot 10^5)$ sayı verilir. Növbəti $q$ sətrinin hər birində iki natural ədəd: $l$ və $r~(1 \le l, r \le n)$ --- maksimumun axtarılacağı parça verilir. \OutputFile Hər bir sorğu üçün verilmiş parçadakı maksimumu verməli.