Games

The annoying-looking part is the alternating game process, but the actual structure is tiny.

A suggestion can have only two outcomes:

• If the game is common to both lists, they immediately stop.
• If the game belongs only to the current player, the suggestion fails and the game continues.

So the common games are not something we count one by one. The first common game suggested is the final move. Boom, game over.

Define:

• $x =$ number of games Alice likes but Bob does not.
• $y =$ number of games Bob likes but Alice does not.

These are the only games that can be used as failed suggestions.

Upper bound from Alice

Alice moves on turns $1, 3, 5, \dots$.

Alice can make at most $x$ failed suggestions, because every failed Alice suggestion must be Alice-only. After she uses all $x$ Alice-only games, her next suggestion must be common, so the process ends.

That means the total number of suggestions can never exceed:

$2x + 1$

Why? Alice can fail on her first $x$ turns, Bob can move between them, and then Alice ends it on her next turn.

Upper bound from Bob

Bob moves on turns $2, 4, 6, \dots$.

Bob can make at most $y$ failed suggestions. After that, Bob's next suggestion must be common and end the process.

Since Bob moves second, this gives another upper bound:

$2y + 2$

So no strategy can beat:

$\min(2x+1,\ 2y+2)$

Now we need to check this is actually achievable, not just a pretty formula doing cosplay as a proof.

Construction

If $x \le y$:

Alice uses all $x$ Alice-only games on her turns. Bob has at least $x$ Bob-only games, so he can answer each time with a failed Bob-only suggestion. Then Alice suggests any common game.

Total:

$2x + 1$

If $x > y$:

Bob is the limiting side. Bob uses all $y$ Bob-only games, while Alice uses $y+1$ Alice-only games. This is possible because $x > y$, so Alice has at least $y+1$ Alice-only games. Then Bob suggests a common game.

Total:

$2y + 2$

That exactly matches the upper bound, so the answer is:

$\boxed{\min(2x+1,\ 2y+2)}$

The sorted order of the input is basically decorative here. Nice of it to show up dressed formally, but we only care about membership.