D. 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. "}] ```json [{"iden":"statement","content":"_这是一个交互式问题。_\n\n你被给定一个按升序排列的单链表。你需要找到链表中大于或等于 $x$ 的最小整数。\n\n更正式地，该单链表基于一个包含 $n$ 个元素的数组构建。索引为 $i$ 的元素包含两个整数：$value_i$ 是该元素的整数值，$next_i$ 是该单链表中下一个元素的索引（如果当前元素是最后一个，则为 $-1$）。链表已排序，即如果 $next_i ≠  - 1$，则 $value_{next_i} > value_i$。\n\n你被给定链表中元素的数量 $n$、第一个元素的索引 $start$ 以及整数 $x$。\n\n你可以进行最多 $2000$ 次以下两种类型的查询：\n\n编写一个解决此问题的程序。\n\n第一行包含三个整数 $n$、$start$、$x$（$1 ≤ n ≤ 50000$，$1 ≤ start ≤ n$，$0 ≤ x ≤ 10^9$）——链表中的元素数量、第一个元素的索引和整数 $x$。\n\n要输出本题的答案，请打印 _! ans_，其中 _ans_ 是链表中大于或等于 $x$ 的最小整数，如果没有这样的整数，则为 _-1_。\n\n要进行第一种类型的查询，请打印 _? i_（$1 ≤ i ≤ n$），其中 _i_ 是你想要查询信息的元素的索引。\n\n每次执行 _?_ 类型的查询后，读取两个整数 $value_i$ 和 $next_i$（$0 ≤ value_i ≤ 10^9$，$-1 ≤ next_i ≤ n$，$next_i ≠ 0$）。\n\n保证如果 $next_i ≠  - 1$，则 $value_{next_i} > value_i$，且数组值构成一个有效的单链表，其中 $start$ 是第一个元素。\n\n请注意，你不能对 _?_ 类型的查询超过 $1999$ 次。\n\n如果 $next_i =  - 1$ 且 $value_i =  - 1$，则表示你询问的查询次数超过了限制，或询问了无效的查询。你的程序应立即终止（例如，调用 _exit(0)_）。你将收到 \"_Wrong Answer_\"，表示你询问的查询次数超过了限制，或询问了无效的查询。如果你忽略这一点，由于你的程序将继续从已关闭的流中读取，你可能会收到其他判题结果。\n\n如果你没有打印任何内容，或忘记 _刷新_ 输出（包括最终答案），你的解决方案将得到 \"Idleness Limit Exceeded\"。\n\n要 _刷新_ 输出，可以在打印查询和换行后使用：\n\n#cf_span(class=[], body=[*Hacks format*])\n\n对于 Hack，使用以下格式：\n\n第一行打印三个整数 $n$、$start$、$x$（$1 ≤ n ≤ 50000$，$1 ≤ start ≤ n$，$0 ≤ x ≤ 10^9$）。\n\n接下来的 $n$ 行，每行打印链表元素的描述：第 $i$ 行打印两个整数 $value_i$ 和 $next_i$（$0 ≤ value_i ≤ 10^9$，$-1 ≤ next_i ≤ n$，$next_i ≠ 0$）。\n\n打印的结构必须是一个有效的单链表。特别是，必须能够从 $start$ 出发，通过跟随 $next_i$ 链接访问所有元素，且最后一个元素 $end$ 的 $next_{end}$ 应为 $-1$。\n\n你可以通过以下链接了解更多关于单链表的信息：https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list \n\n第一个样例的图示。起始和结束元素用黑色标记。 \n"},{"iden":"input","content":"第一行包含三个整数 $n$、$start$、$x$（$1 ≤ n ≤ 50000$，$1 ≤ start ≤ n$，$0 ≤ x ≤ 10^9$）——链表中的元素数量、第一个元素的索引和整数 $x$。"},{"iden":"output","content":"要输出本题的答案，请打印 _! ans_，其中 _ans_ 是链表中大于或等于 $x$ 的最小整数，如果没有这样的整数，则为 _-1_。"},{"iden":"interaction","content":"要进行第一种类型的查询，请打印 _? i_（$1 ≤ i ≤ n$），其中 _i_ 是你想要查询信息的元素的索引。每次执行 _?_ 类型的查询后，读取两个整数 $value_i$ 和 $next_i$（$0 ≤ value_i ≤ 10^9$，$-1 ≤ next_i ≤ n$，$next_i ≠ 0$）。保证如果 $next_i ≠  - 1$，则 $value_{next_i} > value_i$，且数组值构成一个有效的单链表，其中 $start$ 是第一个元素。请注意，你不能对 _?_ 类型的查询超过 $1999$ 次。如果 $next_i =  - 1$ 且 $value_i =  - 1$，则表示你询问的查询次数超过了限制，或询问了无效的查询。你的程序应立即终止（例如，调用 _exit(0)_）。你将收到 \"_Wrong Answer_\"，表示你询问的查询次数超过了限制，或询问了无效的查询。如果你忽略这一点，由于你的程序将继续从已关闭的流中读取，你可能会收到其他判题结果。如果你没有打印任何内容，或忘记 _刷新_ 输出（包括最终答案），你的解决方案将得到 \"Idleness Limit Exceeded\"。要 _刷新_ 输出，可以在打印查询和换行后使用： _fflush(stdout)_ 在 C++ 中； _System.out.flush()_ 在 Java 中； _stdout.flush()_ 在 Python 中； _flush(output)_ 在 Pascal 中； 其他语言请参阅文档。 #cf_span(class=[], body=[*Hacks format*]) 对于 Hack，使用以下格式： 第一行打印三个整数 $n$、$start$、$x$（$1 ≤ n ≤ 50000$，$1 ≤ start ≤ n$，$0 ≤ x ≤ 10^9$）。 接下来的 $n$ 行，每行打印链表元素的描述：第 $i$ 行打印两个整数 $value_i$ 和 $next_i$（$0 ≤ value_i ≤ 10^9$，$-1 ≤ next_i ≤ n$，$next_i ≠ 0$）。 打印的结构必须是一个有效的单链表。特别是，必须能够从 $start$ 出发，通过跟随 $next_i$ 链接访问所有元素，且最后一个元素 $end$ 的 $next_{end}$ 应为 $-1$。"},{"iden":"note","content":"你可以通过以下链接了解更多关于单链表的信息：https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list 第一个样例的图示。起始和结束元素用黑色标记。 "}] ```

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of elements in the list. Let $ s \in \{1, \dots, n\} $ be the index of the first element. Let $ x \in \mathbb{Z}_{\geq 0} $ be the target value. Let $ A = \{(v_i, next_i) \mid i \in \{1, \dots, n\}\} $ be the array representation of the singly linked list, where: - $ v_i \in \mathbb{Z}_{\geq 0} $ is the value stored at index $ i $, - $ next_i \in \{-1\} \cup \{1, \dots, n\} $ is the index of the next element ($ -1 $ if terminal). The list is sorted: for all $ i $, if $ next_i \neq -1 $, then $ v_{next_i} > v_i $. Let $ L = (i_1, i_2, \dots, i_k) $ be the sequence of indices visited starting from $ s $, following $ next $ pointers, until $ next_{i_k} = -1 $. Then $ v_{i_1} < v_{i_2} < \dots < v_{i_k} $. **Constraints** 1. $ 1 \leq n \leq 50000 $ 2. $ 1 \leq s \leq n $ 3. $ 0 \leq x \leq 10^9 $ 4. At most $ 1999 $ queries of type $ ? \, i $ are allowed. 5. All $ v_i $ and $ next_i $ satisfy the linked list validity and sortedness conditions. **Objective** Find the minimum value $ v \in \{v_{i_1}, v_{i_2}, \dots, v_{i_k}\} $ 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, next_i) $. You must output `! ans` as the final answer, where $ ans $ is the found value or $ -1 $.