Time Limit: 1s
Memory Limit: 128MB
WithCS 농장의 아저씨는 N(1 ~ 50,000)명의 강아지를 관리하고 있습니다. 어느날 WithCS 농장 아저씨는 강아지의 건강을 위해 경쟁 프리스비 게임을 하기로 하였습니다.
조 구성을 쉽게 하기 위해 강아지 순서 번호룰 기준으로 연속적으로 묶어 하나의 조으로 만들었습니다. 모든 강아지가 즐겁게 즐기기 위해서는 하나의 조에 속한 강아지들의 키의 차이가 적어야 합니다. WithCS 농장의 아저씨는 Q(1 ~ 200,000)개의 조를 만들었습니다.
각각의 조에 대해 가장 큰 키를 가지는 강아지와, 가장 작은 키를 가지는 강아지의 키 차이를 알고 싶습니다.
* Line 1 : 2개의 정수, N Q
- N : 강아지의 수
- Q : 조(group)의 수
* Line 2 ~ N+1 : 단일 정수 (강아지의 키)
* Line N+1 ~ N+Q+1 : 2개의 정수, A B
- A : 조에 속한 강아지 시작 번호
- B : 조에 속한 강아지 끝 번호
- 예 : "1 5"인 경우 1번 강아지부터 5번 강아지까지 5마리가 한 조로 편성됨
각각의 라인은 Q개의 조 각각에 대해 최소 키와 최대 키의 차이를 기록
6 3 1 7 3 4 2 5 1 5 4 6 2 2
6 3 0