Background

Due to limitations of the Luogu judging environment, please do not submit this problem using the C++ 14 (GCC 9) language, otherwise it may cause compilation errors.

This is an interactive problem.

The gods only gave humans the knowledge to fill their stomachs, yet humans used it to make tools, write words, and grow their city-states. Now they look toward the stars and the abyss...

At every moment they are creating brand-new “knowledge”, and it makes it impossible for me to look away.

I used to think I was good at asking and answering questions, but I gradually understood that many people pretend to be confused even when they understand. The answer to a question cannot help them. As we grow older, do we all lose the courage to face questions and answers...?

Problem Description

The knowledge of the God of Wisdom, Buer, can be represented by a sequence of length $N$: $a_0,a_1,\cdots,a_{N-1}$ (note that indices start from $0$). Unfortunately, mortals cannot窥探 (kuitan, “peer into”) the god’s knowledge: you do not know the value of $N$, nor do you know any value $a_i$.

The God of Wisdom is kind, and Nahida is willing to tell you everything about this knowledge:

• For any $0 \le i < N$, $a_i \neq a_{(i+1)\bmod N}$.
• There exists one and only one $i(0 \le i < N)$ such that both $a_i>a_{(i+1)\bmod N}$ and $a_i > a_{(i+N-1)\bmod N}$ hold at the same time.

You may ask the God of Wisdom questions. In each query, you may give Nahida an integer $k$ in the range $0\sim10^9$, and Nahida will answer with the value of $a_{(d+k)\bmod N}$. Here, $d$ is the index of the element returned by Nahida in the previous query. The initial value of $d$ is set to $0$. For example, if $N=5$ and you give Nahida $1,2,3$ in order, then the returned values are $a_1,a_3,a_1$ in order.

You have $333$ chances to query. You need to find the maximum value in the sequence $a$.

Do you still have the courage to question and to ask?

Implementation Details

The interaction library provides the following functions. You need to declare these functions in your program, but you should not implement their function bodies:

int ask(int k);

• This function returns the value of $a_{(d+k)\bmod N}$ and updates $d$ to $d+k$.

int cheat();

• This function returns the value of $N$.
• If you call this function, you will not be able to get full score for the test point. See the scoring section for details.

You do not need to, and should not, implement the main function. You need to implement the function buer:

int buer(int T);

• T indicates the test point ID.
• When the function ends, you need to return the maximum value of the sequence $a$.

In addition, your submitted program must not try to read from or write to any file or standard streams. Otherwise, you will get $0$ points for this problem. Your program needs to include all required headers and namespaces.

In the final test, for each test point, the interaction library will call the buer function exactly once, and use its return value as the result of your program.

Below is a sample program. It gets $a_1 \sim a_9$ and returns $\max(a_1,a_2)$. You may continue implementing this problem based on it.

#include <vector>
using std::max;
using std::vector;
// Include needed functions from required headers and namespaces.
int ask(int k);
int cheat(); 
// Declare ask and cheat.
int buer(int T) {
	vector <int> vec;
	for(int i = 1; i <= 9; i++) {
		int p = ask(1);
		vec.push_back(p);
	}
	return max(vec[0], vec[1]);
}

It is guaranteed that if the number of calls to ask does not exceed $3333$, the time needed for the interaction library to run in the final test does not exceed $0.2$ seconds, and the memory used by the interaction library itself does not exceed $10$ MiB.

How to Run the Test Program

A reference implementation of the interaction library, grader.cpp, is provided in the problem directory. The interaction library used in the final test is different from this one, so your solution must not rely on the specific implementation details of the interaction library.

After you implement buer.cpp, put grader.cpp and buer.cpp in the same directory, and compile them into an executable using the following commands:

g++ -c grader.cpp -O2 -std=c++14
g++ -c buer.cpp -O2 -std=c++14
g++ grader.o buer.o -o buer -O2 -std=c++14

In the commands above, the first line compiles grader.cpp into the object file grader.o, the second line compiles buer.cpp into the object file buer.o, and the third line links grader.o and buer.o to generate the executable buer.

The executable buer compiled in the above way runs as follows:

• The executable reads testdata from buer.in in the following format:

  • The first line contains two positive integers $N,T$, representing the length of $a$ and the test point ID.
  • The second line contains $N$ positive integers $a_0,a_1,\ldots,a_{N-1}$, representing the sequence $a$.

• If your program finishes normally, the executable writes the following to buer.out:

  • Output one line with two integers, representing the number of queries you made and the return value of the buer function.

When debugging, you need to ensure that the input to the executable buer satisfies the format above. Otherwise, the interaction library is not guaranteed to run correctly.

Input Format

Your submitted program must not try to read from or write to any file or standard streams.

Output Format

Your submitted program must not try to read from or write to any file or standard streams.

4 0
1 2 3 2

3

Hint

Sample Explanation 1

In the sample input provided for this problem, the first line contains two integers $N,T$, representing $N$ and the test point ID. The sample test point IDs are all $0$. The second line contains $N$ integers $a_0,a_1,\cdots,a_{N-1}$, representing the sequence $a$. The sample output is one line with one positive integer, representing the maximum value in the sequence $a$.

Please note that your program must not try to read from or write to any file or standard streams.

Scoring

The final evaluation will only take buer.cpp. Please do not submit any other files in the contestant directory.

This problem will first be subject to the same limits as traditional problems, for example, a compilation error will cause the whole problem to score $0$ points, and runtime errors, exceeding the time limit, exceeding the memory limit, etc. will cause the corresponding test point to score $0$ points.

Besides the conditions above, in a test point, if your program makes an illegal function call or the buer function returns a wrong answer, then that test point will get $0$ points. Otherwise, suppose your program calls the ask function $Q$ times:

• If $0 \le Q \le 333$ and the cheat function is not called, the test point scores $5$ points.

• If $333<Q\le 3333$ and the cheat function is not called, the test point scores $3$ points.

• If $0\le Q \le 333$ but the cheat function is called, the test point scores $2$ points.

• If $333<Q\le 3333$ but the cheat function is called, the test point scores $1$ point.

• If $Q>3333$, the test point scores $0$ points.

Subtasks

For all testdata, it is guaranteed that $2 \le N \le 10^6$, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5