Limited Edition Shop

Rename the objects into points.

For object $x$:

• $A_x$ is its position in Alice's order.
• $B_x$ is its position in Bob's order.

Alice always removes the alive object with minimum $A_x$. Bob always removes the alive object with minimum $B_x$. We choose who moves each turn.

Now list objects in Alice-order:

$c_i = a_i$

and define

$p_i = B_{c_i}.$

So $p_i$ is the Bob-position of the object at Alice-position $i$.

The real constraint

Suppose Alice buys $c_i$.

Before that, every object before $c_i$ in Alice's order must already be gone. If Alice did not buy one of those earlier objects, then Bob must have bought it.

Now suppose Alice buys $c_j$ and later buys $c_i$, where $j < i$, and buys nothing from positions $j+1,\dots,i-1$.

All those skipped objects must be cleared by Bob before Alice can buy $c_i$.

Bob can clear a skipped object $c_t$ before touching $c_i$ only if

$p_t < p_i.$

If $p_t > p_i$, Bob would reach $c_i$ first. Then Bob would buy $c_i$, and Alice's plan is dead. Brutal, but simple.

So the transition $j \to i$ is legal exactly when

$\max(p_{j+1}, p_{j+2}, \dots, p_{i-1}) < p_i.$

For the first object Alice buys, pretend $j=0$.

DP

Let

$dp[i] = \text{maximum total value if Alice's latest bought object is } c_i.$

For each $i$, define $L_i$ as the nearest previous index with

$p_{L_i} > p_i.$

If no such index exists, $L_i = 0$.

Why does this help? Any transition into $i$ must start from some previous Alice-bought position $j$ such that all skipped positions after $j$ have Bob-position less than $p_i$. The nearest earlier blocker with Bob-position greater than $p_i$ is $L_i$, so we need

$L_i \le j < i.$

Therefore:

$dp[i] = v_{c_i} + \max(0, dp[j] \text{ for } L_i \le j < i).$

The $0$ handles starting fresh, and it also prevents negative baggage from coming along for the ride.

The answer is

$\max(0, dp[1], dp[2], \dots, dp[n]),$

because Alice may buy nothing.

Computing $L_i$

Use a monotonic decreasing stack of indices by $p$.

When processing $i$:

• while the stack top has $p < p_i$, pop it
• after popping, the stack top is the nearest previous index with $p > p_i$
• if the stack is empty, $L_i = 0$
• push $i$

Each index is pushed and popped once.

Range maximum

The recurrence needs

$\max(dp[L_i], dp[L_i+1], \dots, dp[i-1]).$

Use a segment tree over Alice positions. Put $dp[0]=0$ at position $0$.

For every $i$:

1. compute $L_i$ with the stack
2. query max DP on $[L_i, i-1]$
3. compute $dp[i]$
4. update position $i$

Correctness

Any valid strategy gives a legal DP path. Between two consecutive Alice-bought positions $j$ and $i$, every skipped object must be removed by Bob before $c_i$. That requires every skipped object's Bob-position to be less than $p_i$, so $j \ge L_i$.

Any DP path is achievable. For each transition $j \to i$, all skipped objects between them have Bob-position less than $p_i$. After Alice buys $c_j$, let Bob move until those skipped objects are gone; Bob will remove them before $c_i$. Then Alice buys $c_i$.

So the DP captures exactly the possible Alice sets, not vibes, not magic.

Complexity:

$O(n \log n)$ per test case, with $O(n)$ memory.