首先我们来分析一下非法情况：

两个不相交的区间最小值都为x，题目又要求序列中的数字互不相同，故非法。

区间A被区间B完全覆盖，且A的最小值小于B的最小值，但注意反过来仍是合法情况。

其中第一种情况可以在线性时间内检查出来，接下来主要讨论第二种情况。我们可以把一个区间最小值的加入看做在当前区间内找到一个空位，空位的最小值小于等于待加入的区间最小值，如果存在这样一个空位说明当前区间最小值合法，否则非法。图2就是一个不存在空位的例子。

显然空位是否存在与区间的最小值有关，我们可以使用线段树维护它。把区间最小值从大到小排序，依次加入线段树，就能检查出第二种情况。对于某个最小值x，需要记录下它的交集和并集。在将它加入线段树时，查询其交集内的最小值是否小于等于x，因为交集是x真正存在的位置。如果最小值小于等于x，说明存在空位，再将其的并集加入线段树，如图2，最小值7的交集可能在5的两侧，但只要并集内出现了比最小值7小的区间就自相矛盾。由于权值是递减的，所以覆盖以前的最小值对接下来的操作没有影响。

接下来还会遇到一个问题就是如何处理出矛盾产生的时间。显然一个矛盾产生的时间取决于组成矛盾的区间中最晚加入的那个。单纯拿线段树维护区间内最晚加入的时间可能导致一些问题：

依次加入的分别是A、C、B，但按照权值排序后A最晚加入，其区间内最晚加入的时间已被修改为B加入的时间，然而在C加入时矛盾就以及产生。

由于问题具有单调性，我们不妨采取二分答案的手段。这样就把问题转化为在当前时间以内加入的区间是否全部合法，只需把在当前枚举的时间之前加入的区间按照上述方法检验一遍即可。

时间复杂度是O(nlog²n)