Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа n и q (1 ≤ n, q ≤ 5×10^5). Следующая строка содержит n целых чисел a[1], ... , a[n] (-5×10^5 ≤ a[i] ≤ 5×10^5, для каждого i ∈ {1, ... , n}), разделенных пробелом. Считайте, что для каждого i ∈ {1, ..., n - 1}: a[i] ≤ a[i+1]. Каждая из следующих q строк содержит один запрос, состоящий из двух целых значений i и j (1 ≤ i ≤ j ≤ n) — границы индексов запроса.

За последним тестом следует строка, содержащая один 0.