Problem Brief

Farthest Seat Assignment

FULLTIMEONSITE INTERVIEW

See Uber online assessment and hiring insights

Design the assignment behavior for a row of n seats numbered from 0 to n - 1. Each call assigns one unoccupied seat to a new employee. The chosen seat must maximize the distance to the nearest occupied seat. If multiple seats have the same best distance, choose the smallest seat index.

Return the first count assigned seats. If count is larger than n, return only the n actual assignments.

1Example 1

Input

n = 10, count = 5

Output

[0,9,4,2,6]

Explanation

The first two assignments take the ends. The third assignment chooses seat 4, which is one of the middle seats farthest from 0 and 9; ties use the smaller index.

2Example 2

Input

n = 3, count = 4

Output

[0,2,1]

Explanation

Only three seats exist, so only three assignments are returned.

Constraints

Limits and guarantees your solution can rely on.

When no seats are occupied yet, assign seat 0.