还是比较有意思的题目。
有一个十分简单的做法，就是考虑直接比较相邻两个数（ 比较， 比较，以此类推）。此时单次需要 次操作，一共需要 次即可确定最大的元素。
这样的总次数是 次，需要询问 轮。我们似乎并不满意。
我们发现，题目限制给了更多的询问次数（ 次），但我们只用掉了其中的 次，浪费了很多次数。
我们可以考虑扩展一下我们的策略。我们考虑不两个两个的比，而是 个 个的比。具体的，假设当前剩下来 个元素，我们将 个元素分成若干个大小为 的组，每个组内部两个元素都比较一遍得到最大值，如果剩下一些元素就单独成一组。
不难发现，我们如果需要区分出来 个元素的最大值，我们需要每两个元素比较一次。相当于是给定一张图，交互库可以给边定向，表示两个点的大小关系，然后你要找到图中最大的那个。
如果你不两两连边，交互库只需要找到不连边的两个点，让所有点都指向这两个点即可。这样我们就不能区分这两个点的大小关系。
但是，我们有很多种分组方式，应该如何选择最优的方法？
我们可以考虑 dp。我们发现只有轮数比较小，因此我们固定轮数最小化询问次数。
令 表示剩下 个元素的大小关系没有区分，剩下 轮需要花多少次询问区分出这些元素。
转移是枚举一个 ，表示将 个元素分成 个元素一组，组内两两比较得到最大值，然后求出来剩下的元素个数以及代价进行转移。
由于很多情况下组数是一样的，因此我们可以考虑整除分块优化一下，只选择个数最少和最多的进行转移，对于剩下组数相同的情况取最小值即可。
但是我们发现这个只能得到 分。
我们重新审视一下这个 DP。假设剩下的组数是 ，那么转移就是 ，其中 是两两比较的代价。而两两比较的代价是 。因此，我们的问题实际上是，对于分成 组的情况，最小化 。
由于一组的代价关于组数是一个二次函数且二次相系数为正，因此这个是一个下凸函数，增长的会越来越快。因此我们最优的方法就是将元素均匀分配到每一组里，如果有分不完的就在一些组里多加一个。
证明可以考虑把权值拆到元素上面。给大小为 的组 增加一个元素的代价是 。因此，给一个组增加元素的代价是越来越大的。
假设当前大小最小的组大小是 ，则此时选择将元素加入 一定不劣。原因是此时加入 更有“决策包容性”。即，加入 后能到达的状态，加入 后也能到达，并且代价还更优秀。
考虑一个此时加入 的解 ，对于每一个解 ，我们都可以构造出一组更加优秀的解 。考察 中的每个操作。
- 此时将元素加入其它的组：那 也加入相同的组。代价差不变。
- 此时将元素加入 组，那么我们此时也将元素加入 组，但是请注意，此时 中的 比 中少一个元素，因此此时解 的代价会比 更小。
- 此时将元素加入 组。还记得 中 比 少一个元素吗？此时我们将这个元素补回来。此时两个解选择的元素集合一定是相同的，因此权值相同，后续的操作直接照搬即可。
我们可以简单延拓一下，这个解法对于下面这个问题也是成立的。
INFO
给定一颗 个节点的有根，你需要在树上选择出 个节点，满足如果选择了 ，那么 的父亲节点也必须选择。这棵树满足儿子节点的权值比父亲节点的权值更大，最小化选择节点的权值和。
证明方法是类似的，只需要将 改成子树即可。
另一个证明方法是交换论证，大致思路是假设最后的解不包含 ，那么从别的地方减掉一些元素下来拼接到 上会更优。
由此可以发现，我们都 个元素一组，剩下的元素自成一组其实并不是最优的。
我们采用新策略进行 DP。每次枚举组数 ，每组元素 个，剩下来 个元素，就给其中 组增加一个元素。
注意到 只有 个不同取值。不妨猜测在元素个数相同的时候代价是关于组数单峰的（分在同一块的情况），最小值只出现在最小组数和最大组数，这样我们就可以整除分块了。
严格证明我不会（不要一头扎进证明里）。但可以感性理解。
感觉上固定轮数 则区分 个元素的代价 应该整体上大致是下凸的，因为看上去区分元素的代价是越来越贵的（这个我不会证，我也不知道对不对）。不过无论如何，这个肯定是单调递增的。
而增加组数的代价造成的代价减少是越来越小的（哎这个我会证）。
考虑从最大的元素头顶取元素组成新的一组。首先取出的元素个数越来越少，其次取出元素的代价越来越小。
不妨考虑取出的第 个元素和第 个元素。首先第 个元素肯定比第 个更小。
首先我们将第 次取出的第 个元素的代价分成两部分，， 是因为加入到一个新的组中需要 的代价。 表示这个元素在原来组中的贡献，因为是取出所以是负的。
假设 次取出来了 个元素，那么这次取出的第 个元素中，肯定有 。这是因为你的最大值会变得越来越小。因此 部分是 次操作减少的更多，而 的部分代价是一样的。而对于 次操作多取出来的一些元素，这些元素显然也会带来负的贡献。 因此 次操作带来的减少是比 次操作带来的减少是更多的。
换句话说，考虑代价函数 表示从 个元素分成 组比较的代价，那么 关于 是下凸的。
另外一方面， 关于 肯定也是下凸的。 假设此时有 组，此时增加一个元素，代价是最小组的大小。而最小组的大小在我们刚刚的贪心下显然是单调不降的。
此外还有，由于在 个组 个元素时增加一个元素的代价是最小组大小，也就是 ，换句话说，，那么考虑 组的情况，就是 。两个式子相减，得到 。
等式右侧显然大于等于 （因为除数更大）。整理一下得到
换句话说， 满足四边形不等式。
以上。如果 下凸，那么两个函数加起来应该也是下凸的，最低点可以二分求出来。
如果 不下凸，那么刚刚已经证明了 满足四边形不等式，上一个四边形不等式优化即可。
反正整除分块能过。
年 月 日更新：和 Claude 讨论之后发现 并不是凸的，反例是 的位置。而块内的最小代价也不总是出现在两端。反例在 ，块 。
但是四边形不等式做法仍然是对的。