不妨设 $x_i$ 有序，则有解的充要条件为 $\sum_{i=1}^nx_i=n(n+1)/2$ 且 $\sum_{i=1}^j x_i\ge j(j+1)/2$ 对任意 $j$ 成立。要构造一个解，首先放 $1,2,\ldots,n$，放了一定的值之后，序列中会出现两个相等的 $x_i$（一定是相邻的），把排列中的两个数交换之后就能构造出这两个数相等的序列。同理，如果某个时刻出现了若干段相等的 $x_i$，则把排列中的每一段翻转即可，最终只会用到 $1,2,\ldots,n$ 以及 $n-1$ 个翻转一些段之后的排列。时间复杂度 $O(n^2)$。