Alice 和 Bob 正在玩一个游戏。Alice 有 $N$ 个物品，编号为 $0$ 到 $N-1$。每个物品的价值是一个非负整数 $A[i]$。

Alice 知道所有物品的价值，但 Bob 只知道物品的数量，并且知道每个价值都是非负整数。Bob 的目标是按照价值的非递减顺序对物品进行排序。也就是说，Bob 需要找到一个长度为 $N$ 的整数数组 $P$，满足以下条件：

• $P$ 中的每个元素互不相同；
• $P$ 中的每个元素都在 $0$ 到 $N-1$（含）之间；
• 对于所有满足 $0 \le i \le N-2$ 的整数 $i$，都有 $A[P[i]] \le A[P[i+1]]$。

为此，Bob 最多可以向 Alice 提问 $10\ 000$ 次。每次提问的过程如下：

1. Bob 放置 $N-1$ 条线，每条线连接两个不同的物品。此时，所有物品必须连通，即可以通过这些线从任意一个物品到达任意另一个物品。
2. Alice 根据以下规则选择一个或多个物品：
   • 她不能选择两个由线直接相连的物品；
   • 在满足上述条件的前提下，被选择物品的价值之和必须最大。
   • 如果存在多个满足条件的选择方案，Alice 会任意选择其中一个并公布。
3. Alice 将被选择的物品告知 Bob，然后移除所有线。

你需要帮助 Bob 以尽可能少的提问次数赢得游戏。

实现细节

你需要实现如下函数：

vector<int> sorting(int N)

• $N$：游戏中的物品数量。

该函数必须返回一个按价值非递减顺序排列的物品编号数组。如果满足条件的数组不唯一，可以返回任意一个。

该函数只会被调用一次。

你可以在函数中调用以下函数：

vector<int> ask_question(vector<array<int, 2>> threads)

该函数表示 Alice 和 Bob 进行一次提问过程。

• threads：大小为 $N-1$ 的数组，每个元素为一个长度为 $2$ 的数组 $[a, b]$，表示在物品 $a$ 和物品 $b$ 之间放置一条线。
• 在 threads 指定的连接关系下，所有物品必须连通。

该函数返回一个长度为 $N$ 的整数数组 $C$。对于每个物品 $i$：

• 若 Alice 在本次提问中选择了物品 $i$，则 $C[i] = 1$；
• 否则 $C[i] = 0$（$0 \le i \le N-1$）。

如果存在多个满足条件的选择方案，评测器会任选一个合法方案返回。注意，在同一个测试用例中，多次用相同的 threads 调用 ask_question 可能会返回不同结果。

在单个测试用例中，ask_question 最多可以被调用 $10\ 000$ 次。

限制

• $5 \le N \le 1\ 000$。
• $A[i]$ 为非负整数（$0 \le i \le N-1$）。注意，$A[i]$ 没有给出上界。
• 在单个测试用例中，ask_question 最多可调用 $10\ 000$ 次。
• 本题采用自适应评测器。这意味着数组 $A$ 并不是固定的，可能会根据对 ask_question 的调用而变化。评测器保证：在每次返回答案时，始终存在至少一个数组 $A$ 与之前所有 ask_question 的结果一致。
• 对于所有测试用例，无论 ask_question 的调用方式如何，评测器的运行时间不超过 $2$ 秒，内存不超过 $16$ MiB。

子任务

评分

子任务 1, 2

在子任务 1 和 2 中，如果 sorting 函数的返回值正确，你将获得该子任务 $100%$ 的分数。

子任务 3, 4, 5

在子任务 3、4、5 中，得分方式如下：

• 如果程序异常终止，或 sorting 函数的返回值错误，则得 $0$ 分。
• 否则，设 $Q_{\max}$ 为在该子任务中，单次执行 sorting 函数时 ask_question 被调用的最大次数。

根据 $Q_{\max}$ 定义 $X$ 如下：

• 若 $10\ 000 < Q_{\max}$，则 $X = 0$；
• 若 $80 < Q_{\max} \le 10\ 000$，则 $X = 90 - 35 \log_{10}\left(\dfrac{Q_{\max}}{80}\right)$；
• 若 $70 < Q_{\max} \le 80$，则 $X = 170 - Q_{\max}$；
• 若 $Q_{\max} \le 70$，则 $X = 100$。

你将获得该子任务 $X%$ 的分数。

样例数据

考虑 $N = 6$，Alice 拥有的物品价值数组为：

$[5, 3, 3, 0, 8, 1]$

评测器首先调用：

sorting(6)

选手代码可能进行如下交互：

ask_question([[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]])
ask_question([[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]])

在第一次调用中，若 Alice 选择物品 $0, 2, 4$，则价值之和为 $5 + 3 + 8 = 16$，为最大值。因此返回：

[1, 0, 1, 0, 1, 0]

在第二次调用中，满足条件的选择集合为 ${1,2,4,5}$ 和 ${1,2,3,4,5}$，因此可能返回：

[0, 1, 1, 0, 1, 1]

或

[0, 1, 1, 1, 1, 1]

考虑以下交互：

ask_question([[0, 1], [2, 3], [4, 5]])
ask_question([[0, 1], [1, 2], [2, 3], [3, 0], [4, 5]])

第一次调用不是合法调用，因为 threads 数组大小不是 $N-1$。

第二次调用也不是合法调用，因为无法通过这些线从物品 $0$ 到达物品 $4$。

满足条件的排序数组有两个：

[3, 5, 1, 2, 0, 4]

[3, 5, 2, 1, 0, 4]

因此函数必须返回其中任意一个。

样例交互库

样例交互库的输入格式如下：

• 第 1 行：$N$
• 第 2 行：$A[0]\ A[1]\ \dots\ A[N-1]$

提供的样例交互库仅在输入为 $0$ 到 $10^9$（含）之间的整数时保证正常运行。

样例交互库将按如下格式输出你在 sorting 函数中返回的数组以及 ask_question 被调用的次数：

• 第 1 行：假设 sorting 函数返回长度为 $M$ 的数组 $P[0]\ P[1]\ \dots\ P[M-1]$，
• 第 2 行：ask_question 函数被调用的次数 $Q$。

注意，样例交互库可能与实际评测使用的交互库不同。