This is a communication problem.

This is a new problem. As everyone should know, this problem comes from JOISC. Since this is a test contest, the problem statement remains unchanged.

There is a permutation $P_0, P_1, \cdots, P_{N-1}$ of length $N$ consisting of integers in the range $[0, N - 1]$. Anna wants to know the index of the minimum element among $P_L, P_{L+1}, \cdots, P_R$. However, Anna only knows the values of $N, L, R$, and does not know the specific information about the permutation $P$.

On the other hand, Bruno knows the value of $N$ and the entire permutation $P_0, P_1, \cdots, P_{N-1}$, but he does not know the values of $L$ and $R$ that Anna is querying.

To allow Anna to obtain this minimum index, Anna and Bruno can send messages to each other. Each character sent between them can only be 0 or 1, meaning each party can send one bit of information at a time. Due to communication equipment limitations, Anna can send at most $18$ bits of information to Bruno, and Bruno can send at most $10\,000$ bits of information to Anna.

Note that the upper bound on the number of bits Bruno sends to Anna is a hard limit used during evaluation. To achieve a full score, the actual number of bits Bruno sends to Anna must not exceed 300.

Write a program to implement the strategy for both Anna and Bruno.

Implementation Details

You need to submit two files.

Anna

The first file you need to submit is Anna.cpp, which implements Anna's strategy. You must include the header file Anna.h and implement the following functions:

void InitA(int N, int L, int R)

This function will be called exactly once for each test case.

• The parameter N represents the length of the permutation $N$.
• The parameters L and R represent the $L$ and $R$ that Anna is querying.

void ReceiveA(bool x)

This function is called whenever Bruno sends a character to Anna.

• The parameter x describes the character sent by Bruno to Anna. true represents 1, and false represents 0.

int Answer()

This function will be called exactly once after the message transmission is complete. This function must return the index of the minimum element that Anna is querying.

In this file, you can call the following function:

void SendA(bool y)

Anna sends a character to Bruno by calling this function.

• The parameter y describes the character sent by Anna to Bruno. true represents 1, and false represents 0.

Bruno

The first file you need to submit is Bruno.cpp, which implements Bruno's strategy. You must include the header file Bruno.h and implement the following functions:

void InitB(int N, std::vector<int> P)

This function will be called exactly once for each test case.

• The parameter N represents the length of the permutation $N$.
• The parameter P describes an array of length $N$. For each $0 \leq i \leq N - 1$, P[i] is the value of $P_i$ in the permutation.

void ReceiveB(bool y)

This function is called whenever Anna sends a character to Bruno.

• The parameter y describes the character sent by Anna to Bruno. true represents 1, and false represents 0.

In this file, you can call the following function:

void SendB(bool x)

Bruno sends a character to Anna by calling this function.

• The parameter x describes the character sent by Bruno to Anna. true represents 1, and false represents 0.

Implementation Details

You can assume that your program will be executed in the following manner:

For each test case, the evaluation system prepares two queues: $Q_Y$ stores characters sent by Anna, and $Q_X$ stores characters sent by Bruno. At the start of the evaluation, InitA and InitB are called, and the characters sent by both parties are placed into the corresponding queues. Subsequently, the following process is repeated:

• If either $Q_X$ or $Q_Y$ is non-empty, a character is popped from the corresponding queue and the corresponding function is called. If both queues are non-empty, one queue is chosen randomly for the corresponding call.
  • Whenever SendA is called, the sent character is pushed into $Q_Y$.
  • Whenever SendB is called, the sent character is pushed into $Q_X$.
• If both queues are empty, the function Answer is called, and the program terminates.

Examples

The sample interaction library will read data from standard input in the following format:

N L R
P[0] P[1] ... P[N-1]

When the program finishes successfully, the sample interaction library will output the following information to standard output:

• If your answer is correct, it will output the total number of characters $Y$ sent by Anna to Bruno and the total number of characters $X$ sent by Bruno to Anna, in the format Accepted: Y X.
• If your answer is incorrect, it will output Wrong Answer[X].

Subtasks

For all data:

• $1 \leq N \leq 1\,000\,000$
• $0 \leq L \leq R \leq N - 1$
• $1 \leq P_i \leq N (0 \leq i \leq N - 1)$
• $P_i \ne P_j (0 \leq i < j \leq N - 1)$

The scores for each subtask are as follows:

• Subtask 1 (1 point): $N \leq 1\,000$
• Subtask 2 (9 points): $N \leq 10\,000$
• Subtask 3 (90 points): No additional restrictions.
  • Let $T$ be the total number of characters sent by Bruno to Anna.
  • Your score for each test case is calculated as follows:
    • If $5\,000 < T \leq 10\,000$, your score is $25 \times \frac{10000 - T}{5000}$
    • If $1\,000 < T \leq 5\,000$, your score is $25 + 40 \times \frac{5000-T}{4000}$
    • If $300 < T \leq 1\,000$, your score is $65 + 25 \times \frac{1000 - T}{700}$
    • If $T \leq 300$, your score is $90$