{"problem":{"name":"D. Interactive LowerBound","description":{"content":"_This is an interactive problem._ You 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_. More forma","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF844D"},"statements":[{"statement_type":"Markdown","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 liked 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\n*   _? i_ (1 ≤ _i_ ≤ _n_) — ask the values _value__i_ and _next__i_,\n*   _! ans_ — give the answer for the problem: the minimum integer, greater than or equal to _x_, or _! -1_, if there are no such integers. Your program should terminate after this query.\n\nWrite a program that solves this problem.\n\n## Input\n\nThe first line contains three integers _n_, _start_, _x_ (1 ≤ _n_ ≤ 50000, 1 ≤ _start_ ≤ _n_, 0 ≤ _x_ ≤ 109) — the number of elements in the list, the index of the first element and the integer _x_.\n\n## Output\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\n[samples]\n\n## Interaction\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_ ≤ 109,  - 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*   _fflush(stdout)_ in C++;\n*   _System.out.flush()_ in Java;\n*   _stdout.flush()_ in Python;\n*   _flush(output)_ in Pascal;\n*   For other languages see documentation.\n\n**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_ ≤ 109).\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_ ≤ 109,  - 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\n## Note\n\nYou can read more about singly linked list by the following link: [https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list](https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list)\n\n<center>The illustration for the first sample case. Start and finish elements are marked dark. ![image](https://espresso.codeforces.com/5fdcc2f8a535c08a9221d03d7e527af8267838c0.png)\n\n</center>","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"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. \"}]\n\n```json\n[{\"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 第一个样例的图示。起始和结束元素用黑色标记。 \"}]\n```","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of elements in the list.  \nLet $ s \\in \\{1, \\dots, n\\} $ be the index of the first element.  \nLet $ x \\in \\mathbb{Z}_{\\geq 0} $ be the target value.  \n\nLet $ A = \\{(v_i, next_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the array representation of the singly linked list, where:  \n- $ v_i \\in \\mathbb{Z}_{\\geq 0} $ is the value stored at index $ i $,  \n- $ next_i \\in \\{-1\\} \\cup \\{1, \\dots, n\\} $ is the index of the next element ($ -1 $ if terminal).  \n\nThe list is sorted: for all $ i $, if $ next_i \\neq -1 $, then $ v_{next_i} > v_i $.  \n\nLet $ 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 $.  \nThen $ v_{i_1} < v_{i_2} < \\dots < v_{i_k} $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 50000 $  \n2. $ 1 \\leq s \\leq n $  \n3. $ 0 \\leq x \\leq 10^9 $  \n4. At most $ 1999 $ queries of type $ ? \\, i $ are allowed.  \n5. All $ v_i $ and $ next_i $ satisfy the linked list validity and sortedness conditions.\n\n**Objective**  \nFind the minimum value $ v \\in \\{v_{i_1}, v_{i_2}, \\dots, v_{i_k}\\} $ such that $ v \\geq x $.  \nIf no such $ v $ exists, return $ -1 $.\n\n**Query Interface**  \nYou may query index $ i \\in \\{1, \\dots, n\\} $ via `? i`, and receive $ (v_i, next_i) $.  \nYou must output `! ans` as the final answer, where $ ans $ is the found value or $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF844D","tags":["brute force","interactive","probabilities"],"sample_group":[["5 3 80\n97 -1\n58 5\n16 2\n81 1\n79 4","? 1\n? 2\n? 3\n? 4\n? 5\n! 81"]],"created_at":"2026-03-03 11:00:39"}}