Description:
This is an interactive problem.
Fox gave Cat two positive integers $$$n$$$ and $$$k$$$. She has a hidden array $$$a_1, \ldots , a_n$$$ of length $$$n$$$, such that $$$1 \leq a_i \leq n$$$ for every $$$i$$$. Now they are going to play the following game:
For any two integers $$$l, r$$$ such that $$$1 \leq l \leq r \leq n$$$, define $$$f(l, r) = (r - l + 1) \cdot \max\limits_{x=l}^r a_x$$$. In other words, $$$f(l, r)$$$ is equal to the maximum of the subarray $$$a_l, \ldots, a_r$$$ multiplied by its size.
Cat can ask Fox at most $$$2 n$$$ questions about the array. He will tell her two integers $$$l$$$ and $$$x$$$ ($$$1 \leq l \leq n, 1 \leq x \leq 10^9$$$), and she will tell him one integer $$$p$$$ as the answer — the smallest positive integer $$$r$$$ such that $$$f(l, r) = x$$$, or $$$n+1$$$ if no such $$$r$$$ exists.
Now, Cat needs to find the largest value $$$m$$$ such that there exists a sequence $$$c_1, \ldots, c_{k-1}$$$ such that $$$1 \leq c_1 < \ldots < c_{k-1} < n$$$ and $$$f(1, c_1) = f(c_1 + 1, c_2) = \ldots = f(c_{k-1}+1, n) = m$$$. If no such $$$m$$$ exists, he should indicate this and take $$$-1$$$ as the answer. Note that for $$$k = 1$$$, $$$m$$$ is always equal to $$$f(1, n)$$$.
In other words, the goal is to find the largest $$$m$$$ such that you can split the array into exactly $$$k$$$ subarrays ($$$k$$$ is the constant given to you in the beginning of the interaction) so that all the subarrays have the product of their length and their maximum equal to $$$m$$$, or determine that no such $$$m$$$ exists. Every element should belong in exactly one of the subarrays.
Cat doesn't know what he should do, so he asked you to play the game for him.
Input Format:
None
Output Format:
None
Note:
The hidden arrays in the three testcases are $$$[1]$$$, $$$[1, 2]$$$ and $$$[1, 3, 6, 1, 2, 1]$$$. In the second testcase, no split satisfies the constraints, so the answer is $$$-1$$$.
The answer for the first query of the third testcase is $$$7$$$ since no valid $$$r$$$ exists. For the second query of the third testcase, since $$$2 \cdot \max(1, 3) = 6$$$, we will get $$$2$$$ as the answer, since $$$r = 1$$$ doesn't satisfy the constraint.
The sample interaction guessed all three answers ($$$1, -1$$$ and $$$6$$$) correctly, so it received $$$1$$$ after each answer.