Description
We have a wooden plank of length n units. Some ants walk left, some walk right at 1 unit per second. When two ants collide, they reverse direction. An ant falls off at position 0 or n. Return the moment when the last ant falls.
Examples
n = 4, left = [4,3], right = [0,1]4Last ant falls at t=4.
n = 6, left = [2], right = [4]4The ant at position 2 moves left and falls off at t=2. The ant at position 4 moves right and falls off at t=2. When ants collide they reverse direction, which is equivalent to passing through each other. The last ant falls at t=4.
n = 5, left = [], right = [1, 3]4Two ants start at positions 1 and 3, both moving right. The ant at position 1 needs 4 seconds to reach position 5 and fall off. The ant at position 3 needs 2 seconds to reach position 5 and fall off. Since they're moving in the same direction and the ant at position 3 is ahead, they won't collide. The last ant to fall is the one that started at position 1, falling at t=4.
Constraints
- •
1 ≤ n ≤ 10^4 - •
0 ≤ left.length ≤ n + 1