First consider only the prefix records . Define by
If is odd for an odd , or if some is outside , the answer is impossible.
For odd , is the median of the first elements. After adding one new element, the old median must remain one of the two middle elements of the new set of size . Hence, for even , the two middle elements are exactly and .
This gives an interval of values allowed for . For , we must have . For even , let and . If , then ; if , then . The case is impossible because the two middle values are distinct.
For odd , let be the two middle values of the previous even-sized prefix. The new median must lie in . If , then ; if , then ; and if , then . Thus is always one integer interval.
Position restrictions alone are not sufficient. Since is an element already present at time , . Also, if the two middle elements of an even prefix are , no value strictly between them may have appeared yet. Therefore, for every , . Collecting these restrictions gives one interval for every value .
Why the prefix conditions are sufficient
The conditions above are also sufficient. Proceed by induction on the prefix length. Suppose an odd prefix has median , and the other middle value required at the next even step is . The deadline condition guarantees that has already appeared, while the release conditions guarantee that no value between and has appeared. Hence is the element immediately below . Adding a new value makes exactly the two middle values. The case is symmetric.
Process the suffix records symmetrically from right to left. According to the parity of the suffix length , define
For an even prefix with middle values , no previously used value lies between them. If the next median is strictly inside the interval, that value itself must be inserted. If the next median is one endpoint, a value must be inserted outside the opposite side. These are exactly the three forms encoded by . Thus every prefix median is correct.
This yields an interval for the value at position , and an interval for each value. Now must occur inside the suffix, so . If an even-length suffix has middle values , every must lie before that suffix, so .
Combining both directions gives one value interval for every position and one position interval for every value. If any intersection is empty, the instance is impossible.
Now fill positions from left to right. Activate a value when . Among active unused values satisfying , choose the one with the smallest .
The greedy choice follows from an exchange property specific to intervals produced by median records. Suppose a feasible completion places at the current position , while the greedy chooses . Let be the position of in that completion. Since the greedy minimizes deadlines, . Because can be placed at , we have , hence . Also .
It remains to check the value interval at position . The derived intervals have the following property: if , both and are locally allowed at , is locally allowed at , but is not, then . This follows by checking the three possible forms of a one-sided local interval. At the first boundary change that separates from , either becomes a determined prefix middle value and therefore must already have appeared, or falls strictly between the two middle values of an even suffix and therefore must appear before that suffix. In both cases this boundary contributes a deadline smaller than to , while remains possible at and hence has deadline at least .
Here , so this separation is impossible. Thus is also allowed at position . Swapping and preserves feasibility, producing a completion that contains the greedy choice. Repeating this argument proves the greedy algorithm.
To build the value-position intervals, the prefix side needs range chmax updates for releases, and the suffix side needs range chmin updates for deadlines. Since only final point values are needed, lazy segment trees that store only pending extrema are sufficient, giving total time.
For the final greedy, store value at coordinate in a segment tree. An active unused value stores the pair ; inactive or used values store infinity. At position , a range-minimum query on gives the greedy choice. If the global minimum deadline ever becomes smaller than , some value has already missed its deadline and the instance is impossible.
After construction, all prefix and suffix medians may be recomputed with Fenwick-tree order statistics as a final consistency check. This does not change the complexity.
The time complexity is and the memory complexity is .
Solution written by GPT5.6