UVa 12174 Shuffle的Shuffle记录

题意：
当前使用的音乐播放软件具备一种所谓的随机播放功能，即对歌曲的播放顺序进行随机排列。假设有n首歌曲，在初始阶段会将这s首歌曲进行随机排序，待全部播放结束后再次进行随机排序并继续播放，依此类推。需要注意的是，在s首歌曲全部播放完成之前不会进行重新排序。因此，播放记录中的每s首歌曲均构成1~s的一个排列。
现提供一个长度为n的播放记录，请判断下一次随机排序可能发生的时间点共有多少种可能性。

例如 s = 4，播放记录为 3 4 4 1 3 2 1 2 3 4，可以发现只存在一种可能性：前两首歌属于某一段的最后两首，之后则是两个完整的段落，因此答案是1。

分析：
本题采用滑动窗口的方法进行处理。

    #include<bits/stdc++.h>
    #define LL long long
    #define ms(s) memset(s, 0, sizeof(s))
    using namespace std;
    const int maxn = 3e5;
    bool valid[maxn];
    int cnt[maxn];
    int pos[maxn];
    
    int main() {
    // freopen("in.txt", "r", stdin);
    // freopen(