**题意翻译**

- **这是一道交互题。**
- 交互库有一个 $[1,n]$ 的排列 $p$。
- 你可以询问 $l,r,k$，交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数。
- 你需要在 $20$ 次询问内找到 $p$ 中 $1$ 的位置。
- $n\in[3,1024]$。

**题目描述**

这个问题与其他两个版本唯一的不同是查询的最大数量。在这个版本中，你最多可以进行 $ \mathbf{20} $ 次查询。只有当所有版本的问题都解决后，你才能进行破解。

这是一个交互问题。

“大家注意！Doremy的完美数据结构课就要开始了！如果你想和我一样聪明，那就努力吧！” 在今天的数据结构课上，Doremy向大家介绍了一种强大的数据结构——Doremy树！现在她给你一个测验，证明你在认真听课。

给定一个长度为 $ m $ 的数组 $ a $，Doremy树支持查询 $ Q(l,r,k) $，其中 $ 1 \leq l \leq r \leq m $ 和 $ 1 \leq k \leq m $，返回数组 $ \left[\lfloor\frac{a_l}{k} \rfloor, \lfloor\frac{a_{l+1}}{k} \rfloor, \ldots, \lfloor\frac{a_r}{k} \rfloor\right] $ 中不同整数的个数。

Doremy有一个从 $ 1 $ 到 $ n $ 的整数的秘密排列 $ p $。你可以进行查询，在每次查询中，你给出 $ 3 $ 个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并获得数组 $ p $ 的 $ Q(l,r,k) $ 值。你可以在最多 $ \mathbf{20} $ 次查询中找到索引 $ y $（$ 1 \leq y \leq n $）使得 $ p_y=1 $ 吗？

注意，排列 $ p $ 在进行任何查询之前都是固定的。

**输入输出格式**

**输入格式**

你首先在第一行读入一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。

**输出格式**

为了进行查询，你应该输出：

- "? $ l\ r\ k $"（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $）

在单独的一行中。每次查询后，你应该读入一个整数 $ x $——$ p $ 的 $ Q(l,r,k) $ 值。在这个问题的版本中，你最多可以进行 $ 20 $ 次这样的查询。为了给出答案，你应该输出：

- "! $ y $"（$ 1 \leq y \leq n $）

在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用：

- 在C++中：fflush(stdout) 或 cout.flush();
- 在Java中：System.out.flush();
- 在Pascal中：flush(output);
- 在Python中：stdout.flush();
- 对于其他语言，请参阅相关文档。

**破解格式**

破解的第一行包含一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。

破解的第二行包含 $ n $ 个不同的整数 $ p_1,p_2,\ldots,p_n $（$ 1 \le p_i\le n $）——排列。

**输入输出样例**

**输入样例 #1**

```
5
2
2
1
3
```

**输出样例 #1**

```
? 1 3 4
? 3 5 3
? 3 4 5
? 3 5 2
! 4
```

**说明**

示例中的排列是 $ [3,5,2,1,4] $。

输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。

在这个交互过程中：

- 对于第一次查询，$ \lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=**题意翻译** - **这是一道交互题。** - 交互库有一个 $[1,n]$ 的排列 $p$。 - 你可以询问 $l,r,k$，交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数。 - 你需要在 $20$ 次询问内找到 $p$ 中 $1$ 的位置。 - $n\in[3,1024]$。 **题目描述** 这个问题与其他两个版本唯一的不同是查询的最大数量。在这个版本中，你最多可以进行 $ \mathbf{20} $ 次查询。只有当所有版本的问题都解决后，你才能进行破解。 这是一个交互问题。 “大家注意！Doremy的完美数据结构课就要开始了！如果你想和我一样聪明，那就努力吧！” 在今天的数据结构课上，Doremy向大家介绍了一种强大的数据结构——Doremy树！现在她给你一个测验，证明你在认真听课。 给定一个长度为 $ m $ 的数组 $ a $，Doremy树支持查询 $ Q(l,r,k) $，其中 $ 1 \leq l \leq r \leq m $ 和 $ 1 \leq k \leq m $，返回数组 $ \left[\lfloor\frac{a_l}{k} \rfloor, \lfloor\frac{a_{l+1}}{k} \rfloor, \ldots, \lfloor\frac{a_r}{k} \rfloor\right] $ 中不同整数的个数。 Doremy有一个从 $ 1 $ 到 $ n $ 的整数的秘密排列 $ p $。你可以进行查询，在每次查询中，你给出 $ 3 $ 个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并获得数组 $ p $ 的 $ Q(l,r,k) $ 值。你可以在最多 $ \mathbf{20} $ 次查询中找到索引 $ y $（$ 1 \leq y \leq n $）使得 $ p_y=1 $ 吗？ 注意，排列 $ p $ 在进行任何查询之前都是固定的。 **输入输出格式** **输入格式** 你首先在第一行读入一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。 **输出格式** 为了进行查询，你应该输出： - "? $ l\ r\ k $"（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $） 在单独的一行中。每次查询后，你应该读入一个整数 $ x $——$ p $ 的 $ Q(l,r,k) $ 值。在这个问题的版本中，你最多可以进行 $ 20 $ 次这样的查询。为了给出答案，你应该输出： - "! $ y $"（$ 1 \leq y \leq n $） 在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用： - 在C++中：fflush(stdout) 或 cout.flush(); - 在Java中：System.out.flush(); - 在Pascal中：flush(output); - 在Python中：stdout.flush(); - 对于其他语言，请参阅相关文档。 **破解格式** 破解的第一行包含一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。 破解的第二行包含 $ n $ 个不同的整数 $ p_1,p_2,\ldots,p_n $（$ 1 \le p_i\le n $）——排列。 **输入输出样例** **输入样例 #1** ``` 5 2 2 1 3 ``` **输出样例 #1** ``` ? 1 3 4 ? 3 5 3 ? 3 4 5 ? 3 5 2 ! 4 ``` **说明** 示例中的排列是 $ [3,5,2,1,4] $。 输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。 在这个交互过程中： - 对于第一次查询，$ \lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=