Mô tả bài toán: Cho một mảng $A$ và một số truy vấn $L_{i}, R_{i}$, yêu cầu tính tổng các phần tử từ phần tử thứ $L_{i}$ đến phần tử thứ $R_{i}$ trong mảng. Tiểu Lam cảm thấy vấn đề này rất nhàm chán, nên cậu muốn sắp xếp lại mảng để tổng kết quả của tất cả các truy vấn càng lớn càng tốt. Tiểu Lam muốn biết, so với mảng ban đầu, tổng tất cả các kết quả truy vấn có thể tăng thêm nhiều nhất là bao nhiêu?

Input: Dòng thứ nhất gồm một số nguyên $n$. Dòng thứ hai gồm $n$ số nguyên $A_{1}, A_{2},..., A_{n}$, giữa hai số nguyên liên tiếp cách nhau bởi một dấu cách. Dòng thứ ba gồm một số nguyên $m$, biểu thị số lượng truy vấn. Tiếp theo là $m$ dòng, mỗi dòng gồm hai số nguyên $L_{i}, R_{i}$, giữa hai số nguyên liên tiếp cách nhau bởi một dấu cách.

Output: Xuất ra một dòng, gồm một số nguyên, biểu thị đáp án.

Input mẫu:

5
1 2 3 4 5
2
1 3
2 5

Output mẫu:

4
Quy mô và ràng buộc test case:
Với 30% test case, n, m \le 50.
Với 50% test case, n, m \le 500.
Với 70% test case, n, m \le 5000.
Với toàn bộ test case, 1 \le n, m \le 10^{5}, 1 \le A_{i} \le 10^{6}, 1 \le L_{i} \le R_{i} \le n.