1479A · Searching Local Minimum

Problem: This is an interactive problem.

Homer likes arrays a lot and he wants to play a game with you.

Homer has hidden from you a permutation $a_1, a_2, \dots, a_n$ of integers $1$ to $n$. You are asked to find any index $k$ ($1 \leq k \leq n$) which is a local minimum.

For an array $a_1, a_2, \dots, a_n$, an index $i$ ($1 \leq i \leq n$) is said to be a local minimum if $a_i < \min\{a_{i-1},a_{i+1}\}$, where $a_0 = a_{n+1} = +\infty$. An array is said to be a permutation of integers $1$ to $n$, if it contains all integers from $1$ to $n$ exactly once.

Initially, you are only given the value of $n$ without any other information about this permutation.

At each interactive step, you are allowed to choose any $i$ ($1 \leq i \leq n$) and make a query with it. As a response, you will be given the value of $a_i$.

You are asked to find any index $k$ which is a local minimum after at most $100$ queries.

Note: In the example, the first line contains an integer $5$ indicating that the length of the array is $n = 5$.

The example makes five "?" queries, after which we conclude that the array is $a = [3,2,1,4,5]$ and $k = 3$ is local minimum.