A sensor logs n distinct integer readings. Starting from an empty binary search tree, insert the readings 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 window queries. Query i gives two integers lo_i and hi_i (lo_i ≤ hi_i); report how many readings x in the tree satisfy lo_i ≤ x ≤ hi_i.

Because q queries must each be answered, an efficient solution augments each tree node with the size of its subtree so a count can be derived from the tree's shape without inspecting every node on every query.

Input format

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

Output format

q lines. Line i contains the count of readings within [lo_i, hi_i].

Constraints

• 1 ≤ n ≤ 40
• -1000 ≤ each reading ≤ 1000, all readings distinct
• 1 ≤ q ≤ 25
• -2000 ≤ lo_i ≤ hi_i ≤ 2000

5
5 3 8 1 4
2
2 5
6 10

3
1

6
10 20 5 15 1 30
3
0 100
16 25
31 40

6
1
0