Có ~n~ địa điểm, địa điểm thứ ~i~ nằm ở tọa độ ~d_i~ trên một trục số. Có ~Q~ truy vấn, mỗi truy vấn cho hai địa điểm ~x~ và ~y~. Cần chọn một địa điểm ~z~ sao cho ~\max(|d_z - d_x|, |d_z - d_y|)~ nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~n~ và ~Q~.
• Dòng thứ hai chứa ~n~ số nguyên ~d_1, d_2, \ldots, d_n~ (không đảm bảo tăng dần).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ (~1 \le x, y \le n~).

Output

Với mỗi truy vấn, in trên một dòng giá trị nhỏ nhất của ~\max(|d_z - d_x|, |d_z - d_y|)~.

Vào/ra bằng file

• Dữ liệu vào: đọc từ file TRAVEL.INP.
• Kết quả: ghi ra file TRAVEL.OUT.