Maksimum

Sizin vəzifəniz çox sadədir: siz yalnız verilmiş parçada maksimumu tapmalısınız.

Giriş verilənləri

İ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.

Çıxış verilənləri

Hər bir sorğu üçün verilmiş parçadakı maksimumu verməli.

Nümunələr