闪烁的繁星
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
背景
繁星闪烁着--深蓝的太空
何曾听得见他们对语
沉默中
微光里
他们深深的互相颂赞了
描述
繁星, 漫天的繁星.
繁星排成一列, 我数一数呀, 一共有N只小星星呢.
星星们是听话的好孩子, 小岛在指挥它们跳舞呢.
舞蹈开始前, 它们都亮了起来!
小岛指一指第i只小星星, 只见第i只小星星立刻改变了自己的状态.
如果它之前是亮着的, 那么立刻就灭掉了.
如果它之前是灭掉的, 现在就立刻亮了呀!
如果说, 可以有连续若干只小星星.
其中任意相邻两只星星状态不同.
那就是最美的了.
小岛希望知道:
每一次发出指令之后
能找到最长的连续小星星, 满足上述需求的
有多长?
格式
输入格式
第一行有两个整数, 分别为星星总数N, 和指令总数Q.
1<=N<=200,000; 1<=Q<=200,000.
之后Q行, 每行有一个整数i: 1<=i<=N, 表示小岛发出的指令.
输出格式
输出有Q行, 其中每i行有一个整数.
表示小岛的第i条指令发出之后, 可以找到的满足要求的最长连续星星序列有多长?
样例1
样例输入1
6 2
2
4
样例输出1
3
5
限制
对于20%的数据: N, Q <= 100.
对于30%的数据: N, Q <= 70000.
对于100%的数据: 1 <= N, Q <= 200,000.
提示
对于样例, 星星序列的状态依次为: OOOOOO -> OXOOOO -> OXOXOO
这里用O表示亮着的星星, 用X表示灭掉的星星.