Cho dãy số nguyên dương \(a\) gồm \(n\) số phân biệt \(a_1, a_2, \dots, a_n\). Cho \(q\) truy vấn, mỗi truy vấn gồm hai chỉ số \(i\) và \(j\).

In ra độ dài cấp số cộng dài nhất của dãy \(a\) mà chứa \(a_i\) và \(a_j\). Các phần tử của cấp số cộng là các phần tử của dãy \(a\), không quan tâm đến vị trí trong \(a\).

Ví dụ: nếu \(a = [2, 6, 5, 1, 4, 8]\), \((i, j) = (1, 5)\) thì \(a_i = 2, a_j = 4\), đáp án là \(4\) (cấp số cộng: \(2, 4, 6, 8\)).

Input

• Dòng đầu ghi hai số \(n, q\) (\(1 \le n \le 1000, 1 \le q \le 10^6\)).
• Dòng thứ hai ghi \(n\) số \(a_i\) (\(1 \le a_i \le 2000\)).
• Mỗi dòng trong \(q\) dòng tiếp theo ghi hai chỉ số \(i\) và \(j\) (\(1 \le i < j \le n\)).

Output

• In ra \(q\) dòng, mỗi dòng là kết quả của từng truy vấn.

Constraints

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 100, q \le 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 1000, q \le 1000\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc bổ sung.

Example

6 7
2 6 5 1 4 8
1 5
1 4
2 3
2 5
4 6
3 4
1 6

4
2
3
4
2
2
4