补题日志
**Codeforces rating：1770 **
- goal：1900
ATcoder rating：1254
- goal：1600
Codeforces Round 915 (Div. 2)
D
不难发现，设当前排列为 \(q_1,q_2\dots q_n\) ，把 \(q_1\) 移到末尾，造成的影响有：
- 对于前缀中 \(\text{mex}_i<q_1\) 的 \(i\) ，移动后不改变它的值。
- 对于前缀中 \(\text{mex}_i>q_1\) 的 \(i\) ，移动后 \(\text{mex}_i=q_1\) 。
- 前缀中不可能存在 \(\text{mex}=q_1\) 的 \(i\)。
- 修改完之后在末尾添加一个 \(n\) 即可。
这样可以用树状数组直接维护每个前缀 \(\text{mex}\) 的出现次数，修改时统计次数+推平即可。
或者采用单调栈维护每个值的出现次数，修改时把大于当前值的暴力合并。
因为段数最多出现 \(n+n\) 次，所以是 \(O(n)\) 的。