Giải đấu

Trong mùa hè năm nay, công ty game AlphaNet sẽ tổ chức giải đấu trực tuyến cho tất cả game thủ của mình. Danh sách tên các game thủ được đánh số thứ tự từ 1 đến $n$. Mỗi game thủ có một ranking (thứ hạng trong game) khác nhau. Trước khi bắt đầu giải, ban tổ chức sẽ cho các game thủ giao lưu với nhau thông qua $q$ lượt đấu đồng đội bằng cách ghép đôi ngẫu nhiên ở mỗi lượt đấu, ban tổ chức thực hiện ghép đôi ngẫu như sau:

• Cho hệ thống sinh ngẫu hiện hai số $u, v$ $(u < v)$ để xác định nhóm các thành viên được chọn tham gia là các game thủ trong danh sách có số thứ tự từ $u$ đến $v$.
• Tiếp theo ban tổ chức sẽ chia nhóm các thành viên được chọn thành 2 đội tương đối đều nhau về ranking.

Ranking của 1 đội là tổng ranking của các thành viên trong đội. Do đó, ban tổ chức phải tính toán để xác định 1 vị trí sao cho đội lệch ranking giữa 2 đội là nhỏ nhất và các thành viên trong đội phải có số thứ tự liên tiếp nhau trong danh sách (không quan trọng số lượng thành viên trong đội).

Yêu cầu: Cho một dãy $n$ game thử với ranking tương ứng và $q$ cặp số nguyên $u, v$ được hệ thông sinh ngẫu nhiên, hãy viết chương trình cho biết độ lệch ranking nhỏ nhất cuả từng lượt sau khi ban tổ chức thực hiện ghép đội ngẫu nhiên.

Đọc từ file GIAIDAU.INP gồm:

• Dòng thứ nhất chứa hai số nguyên dương $n, q$ $(1 \le n, q \le 10^5)$
• Dòng thứ hai chứa $n$ số nguyên dương cách nhau bằng khoảng trắng $a_1, \dots, a_i, \dots, a_n$ $(1 \le a_i \le 10^9)$.

Trên $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $u, v$ $(1 \le u,\ u < v)$ các số trên cùng một dòng cách nhau bằng khoảng trống.

Ghi ra file GIAIDAU.OUT gồm: $q$ dòng, dòng thứ $i$ là kết quả tìm được ở lượt thứ $i$.

• 40% số điểm bài thi: $1 \le n, q \le 100$
• 80% số điểm bài thi: $1 \le n \le 10^3$, $1 \le q \le 10^4$
• 100% số điểm bài thi: $1 \le q \le 10^5$