题目描述

有一个隐藏的长度为 $n$ 的互不相同的序列 $a_1\sim a_n$，经过猜测得到它的最大值和最小值的下标。

你可以猜测任意两个不同下标元素的大小关系。

本题是一道交互题，只能使用 C++ 语言，你不需要也不应该实现 main 函数。

你需要在代码中引入 minmax.h。

你需要实现以下函数：

• std::pair<int,int> sol(int n);
  • 该函数输入一个正整数 $n$，表示序列长度。
  • 该函数需要返回一个数对，分别表示排列中的最大值和最小值。

你可以调用以下函数：

• int guess(int x,int y);
  • 该函数输入两个正整数 $x,y$，其中 $1\le x,y\le n$，$x\ne y$。
  • 该函数返回一个整数：
    • 若返回值为 $-1$，表示 $a_x<a_y$。
    • 若返回值为 $+1$，表示 $a_x>a_y$。
  • 在每组测试数据中，你至多调用此函数 $3000$ 次。

交互库是非自适应的，即原数列在 sol 的调用前即已确定。

样例

考虑以下调用：

• sol(2);

我们进行以下猜测：

• guess(1,2)，返回值为 $1$。

这里我们已经知道排列最大值和最小值的下标，因此返回 $(1,2)$。

数据范围和限制

程序每次运行，sol 函数将会调用 $T$ 次。（$1\le T\le 1000$）。

对 $100\%$ 的数据，$1\le n\le 1000$。

子任务

• （15分）$n\le 30$。
• （35分）$n\le 500$。
• （50分）$n\le 1000$。

开启捆绑测试，并有合理的依赖。

在子任务三中，你可以获得部分分，设每个点询问次数最大值是 $x$，则你可以获得 $f(x)\cdot 50$ 分。

$$f(x) = \begin{cases} 1 & x \leq 1500 \\ 0.8 - \dfrac{0.78}{499}(x - 1501) \quad & 1501 \le x \le 2000 \\ 0.02 & 2000< x\le 3000 \end{cases}$$

注意你的得分是子任务所有测试点的最低分。

样例交互库

本题下发文件中还有一个样例交互库。

样例交互库的输入格式为：

• 第一行一个正整数 $T=1$。
• 第二行一个正整数 $n$，表示长度。
• 第三行 $n$ 个正整数 $a_1\sim a_n$。

不满足交互库输入格式和数据范围的调用未定义。

交互库不会检查你的输入和答案是否合法，且询问次数不设限制。

如果运行正常，交互库会在标准输出（stdout）中输出一行两个正整数表示你的程序的返回值，并在标准输出前向标准错误输出（stderr）中输出询问次数。