Overtaking Maneuvers

You are driving your new car on a highway with two lanes (left and right). Initially, every vehicle – including yours – is in the right lane. There are \(n\) cars ahead of you, each moving at a speed \(v_i\) (with \(V > v_i\), where \(V\) is your car's speed). Because these cars are moving so slowly, you plan to overtake them.

The overtaking rule is as follows: When the front of your car is about to collide with a car ahead, you must take evasive action. In this case, if there is a gap in the right lane that is large enough for your car, you will immediately retreat to (or remain in) the right lane. Otherwise, you will perform a left lane maneuver (i.e. a left turn) in order to overtake.

Note that the vehicles in front may collide. When a faster car from behind catches up with a slower car ahead, a collision occurs and the trailing car reduces its speed to match the front car, forming a group or "fleet" that moves together. The cars are initially arranged in order – from the frontmost to the rearmost.

The key observation is that a left lane maneuver is required each time you encounter a group of cars that have collided into a fleet. In fact, if the \(n\) cars form \(fleets\) (without a gap in between because of collisions), then you will have to perform exactly \(n - fleets\) left lane maneuvers.

Fleet Formation: Assume the cars are equally spaced initially. For any two consecutive cars (given in order from frontmost to rearmost), if the car behind has a speed greater than the current group’s speed, it will eventually catch up and join that fleet. Otherwise, it will maintain its gap and form a new fleet. Therefore, the answer to the problem is simply:

[ \text{Left Maneuvers} = n - (\text{Number of Fleets}) ]

inputFormat

The first line contains two integers \(n\) and \(V\) (where \(1 \leq n \leq 10^5\) and \(1 \leq V \leq 10^9\)); \(n\) is the number of cars ahead and \(V\) is your car’s speed.

The second line contains \(n\) integers \(v_1, v_2, \ldots, v_n\) (with \(1 \leq v_i < V\)) representing the speeds of the cars ahead, given in order from the frontmost car to the rearmost car.

outputFormat

Output a single integer: the number of times your car will perform a left lane (left turn) maneuver.

sample

3 10
3 2 3

1