Перший рядок містить два цілі числа $n$, $q$ ($1 \le n, q \le 2 \cdot 10^5$) --- кількість елементів в масиві і кількість запитів відповідно.

Другий рядок містить $n$ цілих чисел $a_i$ ($1 \le a_i \le 6 \cdot 10^6$) --- опис масиву.

Кожен з наступних $q$ рядків містить по два цілі числа $l$, $r$ ($1 \le l \le r \le n$) --- опис запитів.