생활관 건설하기

최근 생활관 건물이 무너져 내리고 있다는 보고를 받은 중대장 만식이는, 하루빨리 부대의 새로운 생활관을 건설하고자 한다. 부대 내에 생활관을 건설할 부지를 찾아본 결과, $1$번 땅부터 $N$번 땅까지 길이 $1$의 땅이 왼쪽부터 오른쪽까지 일렬로 나열되어 있는 오래된 부지를 발견하였다.

부지 내에 생활관은 단 한 채만 지을 수 있으며, 높이가 동일한 연속한 번호의 땅에 걸쳐 건설해야 한다. 그러나, 오랫동안 방치된 부지였던 만큼 땅의 높이가 제멋대로였다! 따라서 만식이는 부대 내의 병사들을 차출하여 땅의 높이를 같게 만드는 땅 고르기 작업을 진행하고자 한다. $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$줄에 걸쳐, 각 줄에 주어진 구간에 대해 생활관을 건설할 수 있는 땅의 최대 길이를 출력한다.