잠수함

N대의 잠수함이 한 줄로 늘어서서 모두 같은 방향으로 일정한 속도로 항해하고 있다. 이웃한 두 잠수함 사이의 수평 거리는 정확히 5 km이다. 위치는 진행 방향을 따라 1번부터 N번까지 번호가 매겨져 있으며, 1번 위치가 함대의 맨 앞, N번 위치가 맨 뒤이다.

각 잠수함은 서로 다른 깊이에서 항해하며, 깊이는 수면 아래로 밀리미터 단위의 정수로 주어진다. 어떤 잠수함이든 신호를 방송할 수 있다. 한 잠수함이 보낸 신호는 오직 한 대의 잠수함, 즉 그 잠수함보다 뒤에 있고(더 큰 위치 번호) 동시에 더 깊은 잠수함 중에서 가장 가까운 잠수함이 수신한다. 그러한 잠수함이 없으면 신호는 아무도 수신하지 못한다.

잠수함은 크기를 무시한 점으로 간주하며, "가장 가까운"은 유클리드 거리가 가장 작다는 뜻이다. 이웃한 잠수함 사이의 수평 간격 5 km가 전체 깊이 범위보다 크기 때문에, 신호를 수신하는 잠수함은 항상 보낸 잠수함보다 뒤에 있으면서 더 깊은 잠수함 중 위치상 가장 가까운 잠수함이 된다.

제독은 두 종류의 명령을 내릴 수 있다.

• 위치 교환 — 인덱스 i (1 ≤ i < N)가 주어지면, i번 위치의 잠수함과 i+1번 위치의 잠수함이 자리를 맞바꾼다. 이 교환은 시간이 들지 않으며, 각 잠수함은 자신의 깊이를 그대로 유지하고 5 km의 수평 간격도 유지된다.
• 신호 전송 — 모든 잠수함이 동시에 신호를 방송하고, 위에서 설명한 대로 수신된다.

각 신호 전송 명령이 끝난 뒤에, 한 잠수함이 받은 신호의 최대 개수를 출력하라.

첫째 줄에 공백으로 구분된 두 양의 정수 N과 M이 주어진다. N은 잠수함의 수, M은 명령의 수이다.

둘째 줄에 N개의 양의 정수가 주어지며, 이는 1번 위치부터 N번 위치까지 각 잠수함의 깊이이다.

다음 M개의 줄에는 각각 하나의 정수가 주어진다. 값 i > 0은 i번과 i+1번 위치의 잠수함을 맞바꾸는 "위치 교환" 명령이고, 값 0은 "신호 전송" 명령이다.

각 "신호 전송" 명령마다, 그 시점에 한 잠수함이 받은 신호의 최대 개수를 한 줄에 하나의 정수로 출력한다.

1 mm ≤ 각 잠수함의 깊이 ≤ 3 000 000 mm (3 km)

모든 깊이는 서로 다르다.