Cho dãy số nguyên dương ~A_1, A_2, \cdots, A_N~ (~N~ là số chẵn). Giá trị ~A_i~ tương ứng độ năng động của người thứ ~i~. Ta cần chọn ra ~N/2~ cặp đôi để nhảy sao cho mỗi người thuộc đúng một cặp, mỗi cặp có hai người. Gọi ~N/2~ cặp chia được là ~(i_1, j_1), (i_2, j_2), \cdots, (i_{N/2}, j_{N/2})~, khi đó ta định nghĩa "độ thiếu ăn ý" trong một cặp ~(i_k, j_k)~ là ~|A_{i_k} - A_{j_k}|~. Bạn muốn chọn ra ~N/2~ cặp sao cho tổng độ thiếu ăn ý của ~N/2~ cặp là nhỏ nhất có thể. Tuy nhiên bạn lại phát hiện ra ~N/2~ cặp ~(x_i, y_i)~ đặc biệt (họ có thể là "nyc", "cựu mập mờ", hoặc những mối quan hệ nguy hiểm tiềm ẩn!) và sẽ dẫn tới nhiều rủi ro để hai người này nhảy chung nên bạn không được ghép cặp người ~x_i~ với người ~y_i~ lại.

Input

Dòng đầu gồm số nguyên dương ~N~ (~N~ là số chẵn).

Dòng tiếp theo gồm ~N~ số nguyên dương ~A_1, A_2, \cdots, A_N~.

Trong ~N/2~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~x_i, y_i~ là cặp "nguy hiểm" thứ ~i~. Dãy ~x_1, x_2, \cdots, x_{N/2}, y_1, y_2, \cdots, y_{N/2}~ tạo thành một hoán vị của ~\{1, 2, \cdots, N\}~.

Output

Gồm 1 dòng duy nhất gồm tổng độ thiếu ăn ý nhỏ nhất ta có đạt được nếu sắp xếp ~N~ người vào ~N/2~ cặp và không vi phạm vô ~N/2~ cặp nguy hiểm.

Scoring

Trong mọi testcase, điều kiện sau luôn thỏa ~4 \leq N \leq 3 \cdot 10^5, 1 \leq A_i \leq 10^9~.

Sample Input 1

4
1 10 3 4
1 3
2 4

Sample Output 1

10

Sample Input 2

6
1 2 3 4 5 6
1 6
2 5
3 4

Sample Output 2

5

Notes

Ở ví dụ một, ta ghép cặp ~\{1, 2\}~ và ~\{3, 4\}~. Khi đó tổng độ thiếu ăn ý sẽ là ~|10 - 1| + |3 - 4| = 10~.

Ở ví dụ hai, ta ghép gặp ~\{1, 3\}~, ~\{2, 4\}~, và ~\{5, 6\}~. Độ thiếu ăn ý tổng: ~|1 - 3| + |2 - 4| + |5 - 6| = 5~.