A segment tree is a data structure that Ke-lian likes very much. It has a simple structure, excellent complexity, and powerful functionality, so Ke-lian has spent a long time studying some properties of segment trees.

Recently, Ke-lian has started studying segment trees again. The difference is that she is now focusing on a more generalized segment tree: in a standard segment tree, for an interval $[l, r]$, we take $m = \lfloor \frac{l+r}{2} \rfloor$ and split the interval into two sub-intervals $[l, m]$ and $[m + 1, r]$. In a generalized segment tree, $m$ is not required to be exactly the midpoint of the interval, but it must still satisfy $l \le m < r$. It is not difficult to see that in a generalized segment tree, the depth of the tree can reach $O(n)$.

For example, the following tree is a generalized segment tree:

For convenience, we label all nodes in the segment tree according to a pre-order traversal. For example, in the figure above, the label of $[2, 3]$ is 5, and the label of $[4, 4]$ is 9. It is not difficult to see that a generalized segment tree built on $[1, n]$ has a total of $2n - 1$ nodes.

Consider porting the interval localization operation (the process used when applying lazy tags) to the generalized segment tree. It can be seen that the traditional segment tree method for localizing intervals can still be used on a generalized segment tree. For example, in the figure above, the blue nodes and blue edges are the points and edges traversed when localizing the interval $[2, 4]$, and the final localized points are $[2, 3]$ and $[4, 4]$.

If you are not familiar with segment trees, here is a formal definition of the interval localization operation: given an interval $[l, r]$, find the minimum number of disjoint segment tree nodes such that the union of their intervals is exactly $[l, r]$.

Define $S_{[l,r]}$ as the set of nodes obtained by localizing the interval $[l, r]$. For example, in the figure above, $S_{[2,4]} = \{5, 9\}$. Define the distance $d(u, v)$ between two nodes $u$ and $v$ in the segment tree as the number of edges on the shortest path between $u$ and $v$ in the segment tree. For example, in the figure above, $d(5, 9) = 3$.

Now Ke-lian has given you a generalized segment tree on $[1, n]$ and $m$ queries. Each query provides three numbers $u, l, r (l \le r)$, and Ke-lian wants to know $\sum_{v \in S_{[l,r]}} d(u, v)$.

Input

The first line contains an integer $n$.

The next line contains $n - 1$ space-separated integers: the split positions $m$ for all non-leaf nodes in the generalized segment tree, given in increasing order of their labels. It is not difficult to see that these pieces of information uniquely determine a generalized segment tree on $[1, n]$.

The next line contains an integer $m$.

Following this, $m$ lines each contain three integers $u, l, r (1 \le u \le 2n - 1, 1 \le l \le r \le n)$, representing a query.

Output

For each query, output a single integer representing the answer.

Examples

Input 1

10
3 1 2 9 6 4 5 7 8
3
7 6 7
18 4 5
14 5 6

Output 1

7
11
3

Constraints

For 100% of the data, it is guaranteed that $n \ge 2, m \ge 1$.