A till records n distinct integer sale amounts. Starting from an empty binary search tree, insert the sale amounts in the order given, using the standard BST rule: to insert a key x, walk down from the root, going left if x is smaller than the current node and right if x is larger, until an empty spot is reached, where a new node is created. No rebalancing is performed.

You are given q range queries. Query i gives two integers lo_i and hi_i (lo_i ≤ hi_i); its value is the sum of every sale amount x in the tree with lo_i ≤ x ≤ hi_i (0 if none qualify). Report the grand total: the sum of the values of all q queries added together, as a single integer.

Input format

Line 1: an integer n. Line 2: n space-separated distinct integers — the sale amounts, in insertion order. Line 3: an integer q. Next q lines: two space-separated integers lo_i hi_i.

Output format

A single integer: the grand total across all q range queries.

Constraints

• 1 ≤ n ≤ 40
• -300 ≤ each sale amount ≤ 300, all amounts distinct
• 1 ≤ q ≤ 20
• -400 ≤ lo_i ≤ hi_i ≤ 400

5
5 3 8 1 4
2
2 5
0 10

33

4
10 20 5 15
1
6 16

25