Furniture Store

A customer scans sofas from left to right and buys the first sofa with price at most their budget $m$.

That word first is the whole problem. A sofa can be cheap enough and still never get bought, because an earlier affordable sofa blocks it.

When can sofa $i$ be bought?

Suppose a customer buys sofa $i$.

Two things must be true:

1. Sofa $i$ is affordable: $a_i \le m$
2. Every earlier sofa is too expensive, otherwise the customer would stop earlier: $a_j > m \quad \text{for every } j < i$

The second condition means:

$m < \min(a_1, a_2, \dots, a_{i-1})$

So for sofa $i$, we need some budget $m$ satisfying:

$a_i \le m < \min(a_1, a_2, \dots, a_{i-1})$

Such a budget exists exactly when:

$a_i < \min(a_1, a_2, \dots, a_{i-1})$

In plain English: sofa $i$ must be cheaper than every sofa before it.

So the sofas that can be ordered are precisely the new minimum prices while scanning from left to right.

The first sofa is always orderable, because there is nothing before it. Just pick any budget $m \ge a_1$.

For every later sofa:

• If its price is smaller than all previous prices, choose $m = a_i$. All previous sofas are too expensive, so the customer reaches sofa $i$ and buys it.
• If some earlier sofa is cheaper than it, then any budget large enough to afford sofa $i$ also affords that earlier sofa. The customer stops there. Sofa $i$ is cooked.

Algorithm

Maintain the minimum price seen so far, call it mn.

Scan sofas from left to right:

• If $a_i < mn$, sofa $i$ can be ordered, so update mn = a_i.
• Otherwise, sofa $i$ cannot be ordered, so store index $i$.

At the end, print all stored indices.

The indices are naturally collected in increasing order because we scan from left to right.

Complexity

For each test case, we do one scan:

$O(n)$

Memory usage is $O(n)$ for the answer list. With $n \le 100$, this is extremely chill.