가까운 수
시간 제한2초메모리 제한512 MB
순열 p와 q개의 구간 질의 [l, r]가 주어질 때, 부분 배열 p[l..r]에서 두 값의 차이의 최솟값을 구한다.
문제
말나르 씨가 멘사 회원이라는 사실은 널리 알려져 있다. 멘사는 표준 IQ 검사에서 전체 인구의 98%보다 좋은 성적을 받은 사람만 가입할 수 있는 국제 조직이다. 그런데 말나르 씨가 멘자에도 가입되어 있다는 사실은 덜 알려져 있다. 멘자는 연간 식당에서 표준 분량을 먹은 횟수가 인구의 98%보다 많은 사람만 가입할 수 있는 국제 조직이다. 한번은 말나르 씨 본인도 헷갈려서 멘자에 들어갈 때 멘사 회원증을 내밀었다. 이 소식은 멘자의 복도를 빠르게 퍼졌고, 호기심이 많은 일부 회원들은 다음 단체 식사 후에 말나르 씨의 인지 능력을 시험해 보기로 했다.
호기심 많은 회원들은 빈 접시를 모아 n개의 더미를 만들었다. 첫 번째 더미는 접시 1장, 두 번째 더미는 2장, 이런 식으로 n번째 더미는 n장으로 이루어졌다. 그런 다음 그 더미들을 마구 섞었고, 말나르 씨는 q개의 속사포 질문에 답해야 했다. 모든 질문은 같은 형태였는데, "l번째 더미와 r번째 더미 사이에 있는 두 더미의 접시 수 차이 중 가장 작은 값은 얼마인가?"라는 것이었다. 형식적으로, i번째 더미의 접시 수를 pi라고 하면 말나르 씨는 다음을 구해야 한다.
minl≤i<j≤r|pi - pj|
흥미롭게도 말나르 씨는 모든 질문에 2초 안에 답했고, 512 MiB를 넘는 메모리도 쓰지 않았다. 여러분은 분명히 그렇게 못 하겠지만, 어쩌면 그런 프로그램을 작성할 수 있을지도 모른다.
입력
첫째 줄에 문제 본문의 자연수 n과 q가 주어진다. (1 ≤ n, q ≤ 3 · 104)
둘째 줄에 문제 본문의 길이 n인 순열 p가 주어진다.
다음 q개 줄에 자연수 두 개 l과 r이 주어진다. (1 ≤ l < r ≤ n)
출력
i번째 줄에 입력의 i번째 질문에 대한 답을 출력한다.