給定一個(gè)數(shù)組 A 和一些查詢 L_i , R_i，求數(shù)組中第 L_i 至第 R_i 個(gè)元素之和。

小藍(lán)覺得這個(gè)問題很無聊，于是他想重新排列一下數(shù)組，使得最終每個(gè)查詢結(jié)果的和盡可能地大。小藍(lán)想知道相比原數(shù)組，所有查詢結(jié)果的總和最多可以增加多少?

輸入第一行包含一個(gè)整數(shù) n。

第二行包含 n 個(gè)整數(shù) A₁, A₂, · · · , A_n，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。

第三行包含一個(gè)整數(shù) m 表示查詢的數(shù)目。

接下來 m 行，每行包含兩個(gè)整數(shù) L_i、R_i ，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。

5
1 2 3 4 5
2
1 3
2 5

4

原來的和為 6 + 14 = 20，重新排列為 (1, 4, 5, 2, 3) 后和為 10 + 14 = 24，增加了 4。

對于 30% 的評測用例，n, m ≤ 50 ；

對于 50% 的評測用例，n, m ≤ 500 ；

對于 70% 的評測用例，n, m ≤ 5000 ；

對于所有評測用例，1 ≤ n, m ≤ 10⁵，1 ≤ A_i ≤ 10⁶，1 ≤ L_i ≤ R_i ≤ 10⁶ 。