수열과 쿼리 1

길이 $N$의 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.

당신은 $Q$개의 쿼리를 처리해야 한다. 각 쿼리는 두 정수 $l, r$로 주어진다.

쿼리마다 정수 $k$를 $l \le k\le r$가 되도록 하나 고른다. 그 후 길이 $k-l+1$의 정수 수열 $$를 고른다. 는 다음 조건을 만족해야 한다.

첫째 줄에 두 정수 $N, Q$가 공백으로 구분되어 주어진다

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

각 쿼리마다 정답을 한 줄에 하나씩 출력한다.

• $1 \le N, Q \le 150\ 000$
• $-10^9 \le A_i \le 10^9$