It is optimal for each person to do one of the following action:

• Type \(1\): move to the left at a speed of \(1\) until meeting the person to the left, and then move to the right at a speed of \(1\).
• Type \(2\): move to the right at a speed of \(1\) until meeting the person to the right, and then move to the left at a speed of \(1\).

Let us pair two people \(a\) and \(b\) such that the first person \(a\) meets is \(b\) and vice versa (that is, Person \(i\) and \(i+1\) when they do actions of Type \(2\) and \(1\), respectively).
Then, we can prove that we can ignore the scenario where there are two consecutive people that are not paired. At this point, we can solve the problem with one-dimensional dynamic programming in \(O(N)\) time.

Below is the proof of the above fact.

In the figure below, the horizontal axis is the number line, and the vertical axis corresponds to time.
Green, red, purple, and yellow points and lines represent parts of the actions of People \(i - 1, i, i + 1, i + 2\), respectively.
Here, we assume both People \(i\) and \(i + 1\) are unpaired.
If Person \(i - 1\) is of Type \(1\), the green line represents their path after meeting Person \(i - 2\) and turning around. The yellow line represents the path of Person \(i + 2\) similarly, though it is horizontally flipped.

We have assumed that both People \(i\) and \(i + 1\) are unpaired, so we can see that the situation here requires the party to be held until the time at the blue point, as follows:

• If People \(i\) and \(i + 1\) are of Type \(1\) and \(1\), respectively: People \(i + 1\) and \(i + 2\) will meet at the blue point.
• If People \(i\) and \(i + 1\) are of Type \(1\) and \(2\), respectively: People \(i\) and \(i + 1\) will meet at the blue point.
• If People \(i\) and \(i + 1\) are of Type \(2\) and \(2\), respectively: People \(i - 1\) and \(i\) will meet at the blue point.

On the other hand, if we pair People \(i\) and \(i + 1\) here (that is, make them of Type \(2\) and \(1\), respectively), the situation here requires the party to be held until the time earlier than the blue point.
Thus, it is not disadvantageous for us to pair two consecutive people that are unpaired. By repeatedly pairing such people, we can reach a situation without disadvantage where there is at most one person between a pair and the next pair.