Informatica Online Judge

  Epsilon-Delta Query [1914 / 077A]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 9   Total Tried : 9


The Champion of this Problem (C++) : gs16030 - 203ms / 2419byte
My Best Submission (C++) : N/A

[koistudy.net (34th 노규민)]
Writer ID : [gs16030]

Background

규민이는 미적분학 시간에 Epsilon-Delta를 배우고 난 후 흥미를 느꼈고, 이를 활용하기로 결심한다.

규민이에게는 길이 $n$ 배열 $a_0, a_1, cdots a_{n-1}$이 주어져 있고, $Q$개의 쿼리가 들어온다.

각 쿼리는 $c, d$ 두 정수로 들어온다. 단, $0 \le c \le n-1$임이 보장된다.

각 쿼리 $c, d$에 대해서, 규민이가 대답해야 할 값 $l$은, 모든 $|x-c| \le l$을 만족하는 정수 $x$에 대하여, $0 \le x \le n-1$이고 $|a_x-a_c| \le d$인 최대의 $l$이다.

규민이는 귀찮아서 배열의 값을 바꾸는 쿼리는 만들지 않았다. 규민이가 모든 쿼리를 처리할 수 있도록 도와주자.

Input

첫째 줄에는 배열의 길이 $N$과 쿼리의 개수 $Q$가 입력된다. ($1 \le N, Q \le 200000$)
둘째 줄에는 배열 $a_0, a_1, cdots a_{n-1}$이 입력된다. ($0 \le a_i \le 10^9$)
셋째 줄부터 $Q+2$번째 줄까지는 쿼리에 대한 정보가 들어온다.
각 쿼리는 $c, d$ 두 정수로 들어오며, $0 \le c \le n-1$, $0 \le d \le 10^9$임이 보장된다.
20%의 데이터에 대하여, $1 \le N, Q \le 2000$이다.

Output

각 쿼리에 대한 답을 $Q$개의 줄에 순서대로 출력한다.

IO Example

입력 예시 1

5 2
1 7 4 3 5
3 4
4 1

출력 예시 1
1
0

Note. 입력 예시 1은 Case 1이 아니다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]