cs_208 Tìm max các đoạn từ left đến right trong dãy

Cho dãy a gồm n số nguyên và k yêu cầu, trong đó mỗi yêu cầu gồm 2 số L và R.

Nhiệm vụ của bạn là tìm giá trị lớn nhất trong các đoạn từ L đến R trong dãy.

Đầu vào

Dòng đầu tiên chứa số nguyên n và k

Dòng tiếp theo chứa n số nguyên a_i (10^-9<=a[i]<=10^9)

k dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R

Đầu ra

Gồm k giá trị trên 1 dòng, tương ứng với yêu cầu.

Ví dụ

INPUT

10 3

9 2 4 6 -3 8 -20 31 19 10

1 1

9 10

3 5

OUTPUT

9 19 6