NATO, hay Tổ chức Hiệp ước Bắc Đại Tây Dương, là một liên minh quân sự được thành lập vào năm 1949. Đây là một tập hợp các quốc gia từ Bắc Mỹ và châu Âu, ban đầu với mục tiêu chính là đối trọng với sức mạnh và tầm ảnh hưởng của Liên Xô sau Thế chiến II. Nền tảng của NATO là Hiệp ước Bắc Đại Tây Dương, một văn kiện quan trọng xác định các nguyên tắc hoạt động của liên minh. Một trong những điều khoản cốt lõi là Điều 5, một cam kết về phòng thủ tập thể, nghĩa là một cuộc tấn công vũ trang chống lại một quốc gia thành viên sẽ được coi là một cuộc tấn công chống lại tất cả các thành viên. Trong suốt thời kỳ Chiến tranh Lạnh, NATO là một yếu tố răn đe quan trọng, góp phần duy trì sự ổn định giữa hai siêu cường. Sau sự sụp đổ của Liên Xô, NATO đã trải qua quá trình mở rộng và điều chỉnh vai trò, tham gia vào các hoạt động gìn giữ hòa bình, can thiệp nhân đạo và đối phó với các thách thức an ninh mới trên toàn cầu. Ngày nay, NATO vẫn là một liên minh quân sự mạnh với nhiều quốc gia thành viên, tiếp tục đóng vai trò quan trọng trong việc đảm bảo an ninh khu vực và quốc tế.

Tiền thân của NATO: Hiệp ước Brussels là một hiệp ước bảo vệ lẫn nhau giữa các nước Tây Âu để chống lại mối đe dọa ngày càng tăng từ Liên Xô sáng lập vào đầu Chiến tranh Lạnh. Nó được ký kết vào ngày 17 tháng 3 năm 1948 bởi Bỉ, Hà Lan, Luxembourg, Pháp và Vương quốc Anh. Đó là tiền thân của NATO. Mối đe dọa từ Liên Xô trở nên thực sự đáng lo ngại sau vụ phong tỏa Berlin năm 1948, dẫn đến việc thành lập một tổ chức quốc phòng đa quốc gia giữa các nước Tây Âu, Tổ chức Quốc phòng Liên hiệp Phương Tây, vào tháng 9 năm 1948. Tuy nhiên, các nước thành viên của tổ chức lúc đó quá yếu về quân sự để có thể chống lại Lực lượng Vũ trang Liên Xô. Bên cạnh đó, tại Tiệp Khắc vào năm 1948 một cuộc đảo chính của những người cộng sản đã diễn ra thành công và Ngoại trưởng Anh Ernest Bevin tin rằng cách tốt nhất để ngăn chặn các quốc gia khác rơi vào tình trạng như Tiệp Khắc đó là phát triển một chiến lược quân sự giữa các nước phương Tây. Ông có một buổi điều trần tiếp nhận tại Hoa Kỳ, đặc biệt là xem xét sự lo lắng của Mỹ đối với Ý và Đảng Cộng sản Ý.

~n~ quốc gia của NATO đang cần tổ chức họp trong ~q~ ngày để đối phó với một số vấn đề: Tình hình xung đột ở Ukraine, giá nhiên liệu tăng cao, bất đồng quan điểm trong việc ngoại giao với Nga, hay mới nhất là Mỹ áp thuế đối ứng lên hàng hóa thế giới, ...

Trụ sở của các quốc gia thành viên có thể được biểu diễn bằng một đường thẳng, văn phòng của nước thứ ~i~ được đặt tại tọa độ ~x_i~ trên đường thẳng đó. Vào ngày thứ ~k~, các quốc gia từ ~l_k~ đến ~r_k~ sẽ cần gặp mặt để bàn bạc. Họ muốn chọn một tọa độ ~X~ sao cho tổng khoảng cách từ ~X~ đến trụ sở của các quốc gia từ ~l_k~ đến ~r_k~ là nhỏ nhất.

Là một thành viên ẩn của tổ chức, giaminh2211 cần phải tìm ra khoảng cách nhỏ nhất đó để sắp xếp cuộc họp.

INPUT

Dòng đầu chứa hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 2 \times 10^5~)

Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~ (~1 \le x_i \le 10^8~), là tọa độ văn phòng của ~n~ quốc gia thành viên trên đường thẳng.

~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_k, r_k~ (~1 \le l_k \le r_k \le n~), mô tả yêu cầu họp mặt của các quốc gia từ ~l_k~ đến ~r_k~ vào ngày thứ ~k~.

OUTPUT

Với mỗi truy vấn, in ra tổng khoảng cách nhỏ nhất từ một tọa độ ~X~ đến trụ sở của các quốc gia từ ~l_k~ đến ~r_k~ trên một dòng.

SAMPLE INPUT

5 3
13 26 5 6 7
1 3
2 5
3 4

SAMPLE OUTPUT

21
22
1

SUBTASKS