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_{nexti}>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

The first line contains three integers $ n $ , $ start $ , $ x $ ( $ 1

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. Interaction To make a query of the first type, print ? i ( $ 1

You 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) The illustration for the first sample case. Start and finish elements are marked dark.