题目描述

有 N 艘潜艇按同一方向排成一列航行，相邻两艘潜艇的水平距离恒为 5 km。舰队中的位置按航行方向从前到后依次编号为 1 到 N。

每艘潜艇处在某个深度（单位为毫米，整数）。每艘潜艇都可以发出一个广播信号，这个信号只会被满足下列条件的唯一一艘潜艇接收：

• 它位于发信潜艇的后方；
• 它比发信潜艇更深；
• 在所有满足前两条的潜艇中，它与发信潜艇的欧氏距离最近。

如果不存在这样的潜艇，则该信号无人接收。

舰队司令会发出两种命令：

1. swap positions：给定 i (1 <= i < N)，使当前位置 i 与 i+1 的两艘潜艇交换位置。交换瞬时完成，深度不变，交换后两者之间水平距离仍为 5 km；
2. send signal：所有潜艇同时发信。你需要计算：这一轮中，收到信号数最多的一艘潜艇会收到多少个信号。

输入格式

第一行输入两个正整数 N, M，表示潜艇数量和命令数量。

第二行输入 N 个正整数，表示从位置 1 到 N 各潜艇的深度。

接下来 M 行，每行一个整数：

• 若该数为 i > 0，表示执行一次 swap positions，交换位置 i 和 i+1 的潜艇；
• 若该数为 0，表示执行一次 send signal。

输出格式

对于每条 send signal 命令，输出一行一个整数，表示这一轮中单艘潜艇收到信号数的最大值。

数据范围

• 潜艇深度满足 1 mm <= depth <= 3,000,000 mm

子任务

• 子任务 1（20 分）：1 < N <= 1000, 1 <= M <= 100
• 子任务 2（30 分）：1 < N <= 1000000, 1 <= M <= 20
• 子任务 3（50 分）：1 < N <= 1000000, 1 <= M <= 100000

评分说明

只有某个子任务的所有测试点全部通过，才能获得该子任务的分数。

样例

输入

9 3
100 300 50 1000 1100 1200 500 400 600
0
1
0

输出

2
3