非常厉害的一道题。虽然部分分有很强的提示性，但还是不会做。

首先通过部分分引出对这题的一些理解。

" class="headerlink" title="">

此时我们能知道相邻两个数的大小关系，那么在邻居之间连一条大于号边， 之间能确定大小关系当且仅当有一条大于号链连接了它们。

" class="headerlink" title="">

注意到值为 的位置肯定有 ，我们来考察所有 的位置的性质。我们发现 可能为 需要满足 且 前面 个位置的 都不为 。因为 ，这样的位置肯定是唯一的。于是我们能确定 填哪里。然后将 从排列中删掉，更新 ，接着寻找满足条件的位置，我们就能构造出一个满足 数组的排列。根据构造过程容易发现这个排列是唯一的。

实现时从大到小填数，用线段树维护所有的 ，再用个 维护所有 且还没填数的位置，每次选择 中与前驱距离最长的位置即可。容易做到 。

" class="headerlink" title="">

此时我们承袭 时的构造方法，造出一个排列 。但现在每一步选择的位置不一定是唯一的了，仍然能保证构造出合法排列吗？其实是可以的。考察两个相距不超过 的位置 ，容易发现不管构造时选了哪个位置填进当前数，对 和 之间的大小关系都不会产生影响。进一步地，对于所有满足 限制的排列 ， 与 的大小关系都得与 与 之间的大小关系相同。

于是我们确定了任意两对相距不超过 的位置的大小关系，可以仿照 Sub1 的方法连接大于号边，然后跑传递闭包即可。

正解" class="headerlink" title=" 正解"> 正解

此时复杂度瓶颈在于通过跨度（指端点在环上距离）不超过 的大于号边，推出 之间是否存在一条大于号链。考虑位置 与其后面的 个元素。如果 都有大于号边，且这三条边跨度都不超过 ，那我们就不需要 这条边了。在这个原则下，我们只需要找到 后面 个元素中， 最大的且 的元素 ，连一条 的边表示 一定大于 。当然还要找到 前面 个元素中满足条件的 连边。此时我们发现这张图的连通性就等于原图的连通性。但是每个点只会向前连一条边，向后连一条边！

现在边数少了但还要跑传递闭包，这是因为我们还没有用到一条性质：对于一条边 和一个位置 满足 ，我们一定能推出 。结合定义容易发现这是句废话。

但此时我们就可以求解了。首先比较 在 中的大小关系，不妨设 。那么考虑从 开始一直往后跳，跳的过程中仍然保证 。如果最后跳的过程中跨过了 ，说明一定存在一条边满足上面的性质，我们就能推出 一定大于 ，否则就不行。将跳跃的过程使用倍增优化即可做到 。

综上，本题总时间复杂度为 ，代码写起来虽然长但每个部分都不难，主要难点在于思维，需要通过部分分一路想下来，还要有比较强的理解才能做出这道题。

代码：https://loj.ac/s/2003338