CF1746E2.Joking (Hard Version)

The only difference between this problem and the hard version is the maximum number of questions.

This is an interactive problem.

There is a hidden integer $1 \le x \le n$ which you have to find. In order to find it you can ask at most $\mathbf{53}$ questions.

In each question you can choose a non-empty integer set $S$ and ask if $x$ belongs to $S$ or not, after each question, if $x$ belongs to $S$, you'll receive "YES", otherwise "NO".

But the problem is that not all answers are necessarily true (some of them are joking), it's just guaranteed that for each two consecutive questions, at least one of them is answered correctly.

Additionally to the questions, you can make at most $2$ guesses for the answer $x$. Each time you make a guess, if you guess $x$ correctly, you receive ":)" and your program should terminate, otherwise you'll receive ":(".

As a part of the joking, we will not fix the value of $x$ in the beginning. Instead, it can change throughout the interaction as long as all the previous responses are valid as described above.

Note that your answer guesses are always answered correctly. If you ask a question before and after a guess, at least one of these two questions is answered correctly, as normal.

本题与困难版本的唯一区别在于最多可提问的次数。

这是一道交互式题目。

存在一个隐藏的整数 $1 \le x \le n$，你需要找出它。为此，你最多可以提出 $\mathbf{53}$ 个问题。

在每个问题中，你可以选择一个非空整数集合 $S$，并询问 $x$ 是否属于 $S$；每次提问后，若 $x \in S$，你将收到 "YES"，否则收到 "NO"。

但问题在于，并非所有回答都一定为真（其中部分回答是“开玩笑”的），仅保证：对于任意两个连续提出的问题，其中至少有一个的回答是正确的。

此外，除提问外，你最多可进行 $2$ 次对答案 $x$ 的猜测。每次猜测时，若猜中 $x$，你将收到 ":)"，此时你的程序应立即终止；否则你将收到 ":("。

作为“开玩笑”的一部分，我们不会在开始时就固定 $x$ 的值；相反，$x$ 可以在整个交互过程中发生变化，只要所有此前的回答仍满足上述条件（即任意两个连续问题中至少一个回答正确）即可。

注意：你所作的猜测总会得到正确回答。如果你在一次猜测前后各提出一个问题，则这两个问题中至少有一个的回答是正确的（规则同上）。

The only line of the input contains a single integer $n$ ($1 \le n \le 10^5$), the maximum possible value of $x$.

输入仅包含一行，其中有一个整数 $n$（$1 \le n \le 10^5$），表示 $x$ 的最大可能值。

If the answer of the first question were correct, then $x$ would have been equal to $6$, but as we can see in the first guess, $6$ is not the answer.

So the answer of the first question is joking. As we know, the answer of at least one of our two questions is correct, since the answer of the first question was joking, the answer of the second question should be correct.

So we will understand that $x$ is not equal to $1, 2, 3$ or $4$, and we also knew that $x$ is not equal to $6$ either. Hence $x$ should be equal to $5$.

如果第一个问题的答案是正确的，那么 $x$ 就应等于 $6$，但正如我们在第一次猜测中所见，$6$ 并非正确答案。

因此，第一个问题的答案是在开玩笑。我们已知：我们提出的两个问题中，至少有一个问题的答案是正确的；既然第一个问题的答案是在开玩笑，那么第二个问题的答案就一定是正确的。

因此我们可以推断：$x$ 不等于 $1, 2, 3$ 或 $4$；同时我们还知道 $x$ 也不等于 $6$。故 $x$ 应等于 $5$。