CF843B.Interactive LowerBound

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 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.

You are given the number of elements in the list n, the index of the first element start, and the integer x.

You can make up to 2000 queries of the following two types:

• ? i (1 ≤ i ≤ n) — ask the values value__i and next__i,
• ! 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.

Write a program that solves this problem.

这是一个交互式问题。

你将得到一个按升序排列的单向链表。你需要在该链表中找出不小于 $x$ 的最小整数。

更形式化地，该单向链表基于一个包含 $n$ 个元素的数组构建。下标为 $i$ 的元素包含两个整数：$value_i$ 表示该元素存储的整数值，$next_i$ 表示该单向链表中下一个元素的下标（若当前元素为链表末尾，则 $next_i = -1$）。该链表是有序的，即：若 $next_i \neq -1$，则有 $value_{next_i} > value_i$。

你将获得链表中元素的个数 $n$、首元素的下标 $start$，以及整数 $x$。

你最多可进行 2000 次如下两种类型的查询：

• ? i（其中 $1 \le i \le n$）—— 查询下标为 $i$ 的元素的 $value_i$ 和 $next_i$；
• ! ans —— 输出本题的答案：即不小于 $x$ 的最小整数；若不存在这样的整数，则输出 ! -1。你的程序必须在此查询后终止。

请编写一个解决该问题的程序。

The 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$、$start$、$x$（$1 ≤ n ≤ 50000$，$1 ≤ start ≤ n$，$0 ≤ x ≤ 10^9$）—— 分别表示列表中的元素个数、第一个元素的索引以及整数 $x$。

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.

要输出该问题的答案，请输出 ! ans，其中 ans 是列表中大于等于 $x$ 的最小整数；若不存在这样的整数，则 ans 为 $-1$。

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.

你可通过以下链接进一步了解单向链表：https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list

第一个样例的示意图。起始和结束元素用深色标出。