P9139

考虑如果每个数恰好出现两次，那么容易得出一个序列合法当且仅当将每个数两次出现位置看作一个区间 $[l_i,r_i]$ 的两个端点，那么这些区间两两之间不存在包含关系。 考虑每个数出现四次的情况，我们钦定两次为 $i$，两次为 $i+n$，这样可以转化为 $2n$ 的情况，而容易发现只有 $1122$ ......