Tại trung tâm nghiên cứu AI, có hai robot thám hiểm Alpha và Beta đang cần nạp năng lượng. Hệ thống sạc bao gồm các trạm năng lượng nằm trên một trục thẳng, tổng cộng có \(2 \times n\) trạm sạc. Mỗi trạm sạc cung cấp một loại năng lượng thuộc cấp độ từ \(1\) đến \(n\).

Để kích hoạt hệ thống tối thượng, cả Alpha và Beta đều phải lần lượt thu thập đủ bộ năng lượng từ cấp \(1\) đến cấp \(n\) theo đúng thứ tự (tức là phải có cấp \(i - 1\) mới được nạp cấp \(i\)).

Hệ thống vận hành theo quy tắc như sau:

• Ban đầu, hệ thống sẽ đưa hai robot đến vị trí của trạm năng lượng cấp \(1\) gần nhất (chi phí di chuyển ban đầu này được coi là \(0\) hoặc đã được tính toán trong khâu chuẩn bị, không tính vào kết quả).
• Mỗi trạm sạc chỉ phục vụ được cho một robot duy nhất.
• Khoảng cách giữa hai trạm liền kề là \(1\) đơn vị.
• Mục tiêu là điều khiển hai robot di chuyển từ các trạm cấp \(i\) sang các trạm cấp \(i + 1\) sao cho tổng quãng đường cả hai đi được là nhỏ nhất.

Hệ thống đôi khi gặp sự cố và đảo vị trí các trạm sạc cho nhau. Với mỗi thay đổi đó, bạn hãy tính toán lại tổng quãng đường tối ưu.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, q\) (\(1 \le n, q \le 2 \cdot 10^5\)).
• Dòng tiếp theo gồm \(2 \times n\) số nguyên dương \(a_1, a_2, \dots, a_{2n}\) (\(1 \le a_i \le n\)) là cấp độ năng lượng tại các trạm. Dữ liệu đảm bảo mỗi cấp độ xuất hiện đúng 2 lần.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(i, j\) (\(1 \le i < j \le 2n\)) mô tả sự cố hoán đổi trạm sạc ở vị trí \(i\) và \(j\).

Output

• Với mỗi truy vấn hoán đổi, in ra tổng quãng đường nhỏ nhất tìm được.

Example

3 2
1 1 2 2 3 3
2 3
1 4

7
12

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n, q \le 6\).
• Subtask 2 (\(20\%\) số điểm): \(n, q \le 16\).
• Subtask 3 (\(20\%\) số điểm): \(n, q \le 200\).
• Subtask 4 (\(20\%\) số điểm): \(n, q \le 2000\).
• Subtask 5 (\(20\%\) số điểm): không có giới hạn gì thêm.