B. Interactive LowerBound

[{"iden":"statement","content":"_This is an interactive problem._\n\nYou are given a *sorted* in increasing order singly linked list. You should find the minimum integer in the list which is greater than or equal to $x$.\n\nMore formally, there is a singly linked list built on an array of $n$ elements. Element with index $i$ contains two integers: $value_i$ is the integer value in this element, and $next_i$ that is the index of the next element of the singly linked list (or $-1$, if the current element is the last). The list is sorted, i.e. if $next_i ≠  - 1$, then $value_{next_i} > value_i$.\n\nYou are given the number of elements in the list $n$, the index of the first element $start$, and the integer $x$.\n\nYou can make up to $2000$ queries of the following two types:\n\nWrite a program that solves this problem.\n\nThe first line contains three integers $n$, $start$, $x$ ($1 ≤ n ≤ 50000$, $1 ≤ start ≤ n$, $0 ≤ x ≤ 10^9$) — the number of elements in the list, the index of the first element and the integer $x$.\n\nTo print the answer for the problem, print _! ans_, where _ans_ is the minimum integer in the list greater than or equal to $x$, or _-1_, if there is no such integer.\n\nTo make a query of the first type, print _? i_ ($1 ≤ i ≤ n$), where _i_ is the index of element you want to know information about.\n\nAfter each query of type _?_ read two integers $value_i$ and $next_i$ ($0 ≤ value_i ≤ 10^9$, $-1 ≤ next_i ≤ n$, $next_i ≠ 0$).\n\nIt is guaranteed that if $next_i ≠  - 1$, then $value_{next_i} > value_i$, and that the array values give a valid singly linked list with $start$ being the first element.\n\nNote that you can't ask more than $1999$ queries of the type _?_.\n\nIf $next_i =  - 1$ and $value_i =  - 1$, then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling _exit(0)_). You will receive \"_Wrong Answer_\", it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.\n\nYour solution will get \"Idleness Limit Exceeded\", if you don't print anything or forget to _flush_ the output, including the final answer.\n\nTo _flush_ you can use (just after printing a query and line end):\n\n#cf_span(class=[], body=[*Hacks format*])\n\nFor hacks, use the following format:\n\nIn the first line print three integers $n$, $start$, $x$ ($1 ≤ n ≤ 50000$, $1 ≤ start ≤ n$, $0 ≤ x ≤ 10^9$).\n\nIn the next $n$ lines print the description of the elements of the list: in the $i$-th line print two integers $value_i$ and $next_i$ ($0 ≤ value_i ≤ 10^9$, $-1 ≤ next_i ≤ n$, $next_i ≠ 0$).\n\nThe printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from $start$ by following links $next_i$, and the last element $end$ should have $-1$ in the $next_{end}$.\n\nYou can read more about singly linked list by the following link: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list \n\nThe illustration for the first sample case. Start and finish elements are marked dark. \n"},{"iden":"input","content":"The first line contains three integers $n$, $start$, $x$ ($1 ≤ n ≤ 50000$, $1 ≤ start ≤ n$, $0 ≤ x ≤ 10^9$) — the number of elements in the list, the index of the first element and the integer $x$."},{"iden":"output","content":"To print the answer for the problem, print _! ans_, where _ans_ is the minimum integer in the list greater than or equal to $x$, or _-1_, if there is no such integer."},{"iden":"interaction","content":"To make a query of the first type, print _? i_ ($1 ≤ i ≤ n$), where _i_ is the index of element you want to know information about. After each query of type _?_ read two integers $value_i$ and $next_i$ ($0 ≤ value_i ≤ 10^9$, $-1 ≤ next_i ≤ n$, $next_i ≠ 0$). It is guaranteed that if $next_i ≠  - 1$, then $value_{next_i} > value_i$, and that the array values give a valid singly linked list with $start$ being the first element. Note that you can't ask more than $1999$ queries of the type _?_. If $next_i =  - 1$ and $value_i =  - 1$, then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling _exit(0)_). You will receive \"_Wrong Answer_\", it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream. Your solution will get \"Idleness Limit Exceeded\", if you don't print anything or forget to _flush_ the output, including the final answer. To _flush_ you can use (just after printing a query and line end): _fflush(stdout)_ in C++; _System.out.flush()_ in Java; _stdout.flush()_ in Python; _flush(output)_ in Pascal; For other languages see documentation. #cf_span(class=[], body=[*Hacks format*]) For hacks, use the following format: In the first line print three integers $n$, $start$, $x$ ($1 ≤ n ≤ 50000$, $1 ≤ start ≤ n$, $0 ≤ x ≤ 10^9$). In the next $n$ lines print the description of the elements of the list: in the $i$-th line print two integers $value_i$ and $next_i$ ($0 ≤ value_i ≤ 10^9$, $-1 ≤ next_i ≤ n$, $next_i ≠ 0$). The printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from $start$ by following links $next_i$, and the last element $end$ should have $-1$ in the $next_{end}$."},{"iden":"note","content":"You can read more about singly linked list by the following link: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list The illustration for the first sample case. Start and finish elements are marked dark. "}]}

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of elements in the list. Let $ \text{start} \in \{1, \dots, n\} $ be the index of the first element. Let $ x \in \mathbb{Z}_{\geq 0} $ be the target value. Let $ V: \{1, \dots, n\} \to \mathbb{Z}_{\geq 0} $ be the value function, where $ V(i) $ is the integer stored at index $ i $. Let $ N: \{1, \dots, n\} \to \{-1\} \cup \{1, \dots, n\} $ be the next-pointer function, where $ N(i) $ is the index of the next element, or $-1$ if $ i $ is the last. The list is sorted: for all $ i \in \{1, \dots, n\} $, if $ N(i) \neq -1 $, then $ V(N(i)) > V(i) $. **Constraints** 1. $ 1 \leq n \leq 50000 $ 2. $ 1 \leq \text{start} \leq n $ 3. $ 0 \leq x \leq 10^9 $ 4. At most $ 1999 $ queries of type $ ?\ i $ are allowed. 5. For all $ i \in \{1, \dots, n\} $, $ V(i) \geq 0 $, and $ N(i) \neq 0 $. **Objective** Find the minimum value $ v \in \{V(i) \mid i \in \{1, \dots, n\}\} $ such that $ v \geq x $. If no such $ v $ exists, return $ -1 $. **Query Interface** You may query index $ i \in \{1, \dots, n\} $ via `? i`, and receive $ (V(i), N(i)) $. You must output the answer via `! ans`, where $ \text{ans} \in \{-1\} \cup \{V(i) \mid i \in \{1, \dots, n\}\} $ and $ \text{ans} \geq x $ or $ \text{ans} = -1 $.