Alternate Driving Journey

Two friends, A and B, plan an eastward road trip through n cities. The cities are numbered from 1 to n from west to east. Each city i has a unique altitude \(h_i\). The distance between city \(i\) and city \(j\) is \(d_{i,j} = |h_i - h_j|\). They choose a starting city \(s\) and drive eastward (to cities with larger numbers) until the total distance traveled would exceed a given limit \(x\; km\>.

The two take turns driving. On the first day, A drives, and then they alternate each day. Their driving strategies differ:

• A's strategy: At his turn, he selects the second closest city (in terms of \(d_{i,j}\)) among all cities to the east of the current city. (If there is a tie in distance, the city with the lower altitude is considered closer.) If there is fewer than two cities available, he cannot make a move and the journey ends.
• B's strategy: At her turn, she always selects the nearest city among the ones to the east. (Using the same tie-breaking rule.)

Before setting off, A wants to know:

1. For a given \(x = x_0\), which starting city \(s\) minimizes the ratio of the total distance driven by A to that driven by B (i.e. \(\frac{D_A}{D_B}\))? If B's driving distance is 0, consider the ratio to be \(\infty\) (and all \(\infty\) are equal). If there are multiple starting cities with the same minimum ratio, choose the one with the highest altitude.
2. For any given \(x = x_i\) and starting city \(s_i\), what are the total distances driven by A and B?

The journey simulation works as follows. Starting from a city \(s\), let the total distances for A and B be initially 0. At each step, let the current city be c. Consider all cities with indices greater than c (i.e. all cities to the east). For each candidate city \(j\), let \(d = |h_c - h_j|\). Sort these candidates in increasing order of \(d\), using the altitude (lower first) as a tie-breaker.

If it is A's turn and there are at least two candidates, he chooses the second candidate; if it is B's turn, she chooses the first candidate. Before moving, if adding the distance to the chosen city would make the total distance (sum of both drivers) exceed \(x\), the journey ends immediately. Otherwise, add the distance to the corresponding driver's total and continue from the chosen city, switching turns. The journey also ends if a driver cannot choose a city based on his/her strategy.

inputFormat

The input begins with an integer \(n\) (the number of cities). The next line contains \(n\) distinct integers \(h_1, h_2, \dots, h_n\) representing the altitudes of cities 1 through \(n\) in order from west to east.

The following line contains an integer \(q\) indicating the number of queries. Each of the next \(q\) lines represents a query in one of the following two formats:

• 1 x: For the given travel distance limit \(x = x_0\), determine the starting city \(s\) (\(1 \le s \le n\)) that minimizes the ratio \(\frac{D_A}{D_B}\) (with \(D_B = 0\) treated as \(\infty\)). In case of a tie, choose the starting city with the highest altitude.
• 2 x s: For the given travel limit \(x = x_i\) and starting city \(s = s_i\), simulate the journey and output two integers: the total distance driven by A and the total distance driven by B.

Note: All distances are measured in kilometers, and \(x\) is an integer.

outputFormat

For each query, output one line:

1. For a query of type 1, output a single integer denoting the optimal starting city number.
2. For a query of type 2, output two space-separated integers: the total distance driven by A and by B respectively.

sample

5
10 20 15 30 25
3
1 50
2 50 1
2 50 3

1
25 10
15 5

</p>