The first line contains two integers $n$, $q$ ($1 \le n, q \le 2 \cdot 10^5$) --- the number of elements in the array and the number of queries, respectively.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 6 \cdot 10^6$) --- the description of the array.

Each of the next $q$ lines contains two integers $l$, $r$ ($1 \le l \le r \le n$) --- the description of the queries.