Maksimum — Eolymp

Giriş

İlk satır, dizideki eleman sayısını belirten bir $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) tam sayısını içerir.

İkinci satır, dizinin elemanları olan $a_{1}, a_{2}, \dots, a_{n} (- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ a_1, a_2, \ldots, a_n~(-10^9 \le a_i \le 10^9) tam sayılarını içerir.

Üçüncü satır, sorgu sayısını belirten bir $q (1 \leq q \leq 5 \cdot 1 0^{5})$ q~(1 \le q \le 5 \cdot 10^5) tam sayısını içerir.

Sonraki $q$ satırın her biri, bir aralığın uç noktalarını temsil eden iki pozitif tam sayı $l$ ve $r (1 \leq l, r \leq n)$ r~(1 \le l, r \le n) içerir. Her sorgu için, $l$ ile $r$ arasındaki (dahil) alt dizideki maksimum değeri bulmanız gerekmektedir.

Çıktı

Her sorgu için, ilgili aralıktaki maksimum değeri yazdırın.

Örnekler

Örnek 1

Loading