|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||128 MB||0||0||0||0.000%|
Fleet of N submarines is cruising in the ocean. The submarines are aligned in a row and are moving with constant speed in the same direction. The horizontal distance between each two consecutive submarines is 5 km. The positions in the fleet are numbered from 1 to N in the direction of the movement (position with number 1 is the first in the fleet and position with number N is the last in the fleet). Each submarine is moving at different depth, measured in millimeters under the ocean’s surface (integer number). Each submarine can send a broadcast signal which is received only by the closest submarine which is moving behind the one sending the signal and is also deeper than it. If such submarine does not exist the signal is not received by anyone.
Explanation: The submarines are considered points – their dimensions are ignored. The closest submarine is the one that has the smallest Euclidean distance from the submarine that is sending the signal.
The Admiral of the fleet can issue two types of commands:
Write a program submarines, which after each command of type “send signal”, computes the maximum number of signals that are going to be received by a single submarine.
Two positive integers N and M , separated by an interval, are given on the first row of the standard input: N is the number of the submarines in the fleet and M is the number of issued commands.
There are N positive integers on the second row – the depths on which the submarines are traveling from position 1 to N.
On each of the next M rows a single integer number is given. If the number is i>0, this is a “swap position” command and submarines on positions i and i+1 must change their positions; if the number is 0 – this is “send signal” command.
1 mm ≤ depth of the submarines ≤ 3 000 000 mm (3 km)
1 < N ≤ 1 000 000, 1 ≤ M ≤ 100 000
For each command “send signal” your program must output a single integer on a separate row of the standard output – the computed maximum number of signals that will be received by a single submarine.
9 3 100 300 50 1000 1100 1200 500 400 600 0 1 0