Original proposer: vwxyz

For each chair, determine if the conditions are satisfied.
To inspect the chair to the left and right, we may implement a conditional branch, but the idea of sentinel simplifies the implementation.

Place an empty chair to the left of the leftmost chair.
Place an empty chair to the right of the rightmost chair, too.
In the implementation, this can be realized by prepending and appending an x to \(S\).
Now, it suffices to inspect the \(N\) chairs other than the additional ones if the following conditions are satisfied:

• The seat itself is empty.
• The seat to its left is empty.
• The seat to its right is empty.

Now we do not have to implement a conditional branch for the \(1\)-st and \(N\)-th chairs from the left.

In this problem, implementing a conditional branch and using a sentinel are not very different, but it is common in more difficult problems where such a technique significantly reduces the implementation effort.