생활관 건설하기

최근 생활관 건물이 무너지고 있다는 보고를 받은 중대장 만식이는 하루빨리 부대의 새 생활관을 짓고자 한다. 부대 안에서 부지를 찾아보니, 길이가 $1$인 땅이 $1$번부터 $N$번까지 왼쪽에서 오른쪽으로 일렬로 놓인 오래된 부지가 있었다.

생활관은 부지에 한 채만 지을 수 있으며, 높이가 같은 연속된 번호의 땅 위에 지어야 한다. 그러나 오랫동안 방치된 부지라 땅의 높이가 제각각이다. 그래서 만식이는 병사를 투입해 땅을 고르고 높이를 같게 맞추려 한다. $i$번 땅의 높이는 $h_i$이고, 각 땅의 높이를 $x$만큼 높이거나 낮추려면 그 땅에서 $x^2$명의 병사가 작업해야 한다. 높이는 반드시 정수만큼만 바꿀 수 있다. 현재 부대의 병사는 $M$명뿐이므로, 만식이는 최대 $M$명의 병사만 작업에 투입하여 생활관을 지을 수 있는 땅의 길이를 최대화하려 한다.

그런데 작업 직전, 본부에서 공문이 내려왔다. 생활관은 부지 내 $l$번 땅부터 $r$번 땅까지 구간 $[l, r]$ 안의 땅에만 지을 수 있다는 내용이다. 공문의 숫자가 깨져서 $l$과 $r$을 정확히 읽을 수 없었다. 재발송을 기다릴 수 없었던 만식이는 미리 $Q$개의 구간 $[l_j, r_j]$마다 생활관을 지을 수 있는 땅의 최대 길이를 구하려 한다. 만식이를 위해 $Q$개의 질문에 답하라.

첫 번째 줄에 부지의 길이 $N$과 병사 수 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 500\,000$, $1 \leq M \leq 10^{18}$)

두 번째 줄에 각 땅의 높이 $h_1, h_2, \cdots, h_N$이 공백으로 구분되어 주어진다. ($1 \leq h_i \leq 1\,000\,000$)

세 번째 줄에 질문의 개수 $Q$가 주어진다. ($1 \leq Q \leq 500\,000$)

이후 $Q$줄에 걸쳐 각 줄에 구간의 범위 $l_j$와 $r_j$가 공백으로 구분되어 주어진다. ($1 \leq l_j \leq r_j \leq N$)

$Q$줄에 걸쳐, 각 줄에 $j$번째 구간에서 생활관을 지을 수 있는 땅의 최대 길이를 출력한다.