A wooden plank of length n units is placed horizontally. Several ants are walking on the plank, with each ant moving at a constant speed of $1$ unit per second. Some ants move towards the left, while others move towards the right.

When two ants moving in opposite directions meet, they immediately change their directions and continue moving at the same speed. An ant falls off the plank if it reaches position $0$ while moving left or position n while moving right.

Given the integer n and two integer arrays left and right, representing the starting positions of the ants moving left and right respectively, return the moment when the last ant falls off the plank.

Constraints:

• $1 \leq$ n $\leq 10^4$

• $0 \leq$ left.length $\leq$ n $+ 1$

• $0 \leq$ left[i] $\leq$ n

• $0 \leq$ right.length $\leq$ n $+ 1$

• $0 \leq$ right[i] $\leq$ n

• $1 \leq$ left.length $+$ right.length $\leq$ n $+ 1$

• All values of left and right are unique, and each value can appear only in one of the two arrays.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.