A chain of $N$ deep-space relay beacons is strung along a signal corridor, numbered from $1$ to $N$. Each beacon $i$ registers a signal strength $A_i$. Because the corridor focuses the transmission at a single point, the readings first rise strictly and then fall strictly: there is exactly one index $p$ such that

$A_1 < A_2 < \dots < A_{p-1} < A_p > A_{p+1} > \dots > A_N$.

Your task is to find $p$, the beacon at the focal point. The readings themselves are hidden; you may only sample them one at a time.

You are provided with a function int strength(int i), which returns the signal strength $A_i$ registered by beacon i.

Implement the function int peak(int N), which should return the index of the beacon with the highest signal strength.

Input

The grader provides a single integer $N$, the number of beacons. The readings $A_1, \dots, A_N$ are hidden and accessible only through strength(int i).

Output

Your function should return the index of the peak beacon as an integer.

Constraints

• $1 \le N \le 10^6$
• $1 \le A_i \le 10^9$ for all $i$
• $1 \le i \le N$ for every call to strength(int i) (sampling outside this range is a runtime error).
• You may call strength(int i) at most $29$ times.
• The readings are strictly unimodal: they strictly increase up to the peak and strictly decrease after it. The increasing or decreasing side may be empty.

Scoring

For each test case, your solution scores 100 if it returns the index of the peak beacon and makes at most $29$ calls to strength(int i). If it reports an incorrect index, or makes more than $29$ calls, the score for that test case is 0.

The score for a submission is the minimum score obtained over all test cases.

Sample Grader

The sample grader reads an integer $N$, followed by $N$ integers $A_1, \dots, A_N$, the hidden readings.

It then prints the index returned by int peak(int N), followed by the number of calls made to int strength(int i).