Find the Maximum Common Ancestor in a Parameterized Tree

You are given a positive integer n and an integer sequence a₁, a₂, ..., a_n satisfying \[ \frac{i(i-1)}{2} < a_i \le \frac{i(i+1)}{2} \] for each 1 \le i \le n. This sequence parameterizes a rooted tree that has n+1 levels and a total of \(\frac{(n+1)(n+2)}{2}\) nodes. Specifically, the i-th level contains nodes numbered from \[ \frac{i(i-1)}{2}+1 \quad \text{to} \quad \frac{i(i+1)}{2} \] (inclusive). Furthermore, in the i-th level (for 1 \le i \le n), the node with value a_i (which lies in that level) is special and has two children, while every other node in the same level has exactly one child. The children are assigned in order from left to right.

You are then given q queries. Each query consists of two node values x and y. For each query, find their maximum common ancestor (i.e. the common ancestor with the greatest value).

Note: The tree is constructed level by level as follows:

• Level 1: Contains only the root node (which is necessarily a₁ = 1 by the given condition).
• For 1 \le i \le n, the i-th level has i nodes. In that level, the special node is a_i (its position in the level is a_i - \(\frac{i(i-1)}{2}\)). When creating level i+1, iterate over the nodes in level i from left to right. For every node:
• If it is the special node, assign it 2 children.
• Otherwise, assign it 1 child.
• This way, level i+1 gets exactly i+1 nodes.

To answer a query, you may simulate the process of finding the parent of a given node. For any node x that lies in level L (i.e. \(\frac{(L-1)L}{2} < x \le \frac{L(L+1)}{2}\)), its parent (if L > 1) is determined using the following method:

1. Let pos be the position of x in its level:
   \(pos = x - \frac{(L-1)L}{2}\) (1-indexed).
2. Let the special node in the parent level (level L-1) be a_L-1. Its position in that level is: \[ sp = a_{L-1} - \frac{(L-2)(L-1)}{2} \]
3. Then the index j (1-indexed) of the parent in level L-1 is determined by:
   - If pos < sp then j = pos.
   - If pos == sp or pos == sp+1 then j = sp.
   - Otherwise (i.e. if pos > sp+1), j = pos - 1.
4. The parent's value is then: \[ parent(x) = \frac{(L-2)(L-1)}{2} + j \]

You can then find the maximum common ancestor (MCA) of two nodes by repeatedly lifting the deeper node until both nodes are in the same level, and then moving both up until they meet.

inputFormat

The input begins with a line containing a positive integer n (the length of the parameterizing sequence). The next line contains n space-separated integers, representing a₁, a₂, ..., a_n.

The following line contains a positive integer q, the number of queries. Each of the next q lines contains two space-separated integers x and y, representing a query.

outputFormat

For each query, output the value of the maximum common ancestor of x and y on a new line.

sample

3
1 2 6
3
4 5
4 6
5 6

2
1
1