Minimal Moves Victory in the Card Train Game

This problem is based on a card game called "Card Train" (also known as "Drag the Truck" and "Cat Fishing"). In this game there are \(2n\) cards. For every integer \(1 \le i \le n\), there are exactly two cards with value \(i\). Initially, player I and player J each receive \(n\) cards. Player I gets the complementary multiset of the cards that player J holds. The game also has a common public pile (which may be thought of as a stack) that starts empty.

The game proceeds in turns. Player I takes the first turn, and then the players alternate. In each move the current player performs the following steps in order:

1. The player chooses a card from his/her hand and places it on top of the public pile.
2. If after placing the card the public pile contains two cards with the same value, then the substack starting from the lower occurrence of that card up to the top of the pile (including both the matching cards and any cards between them) is removed from the public pile and added to the current player's hand. For player J, the collected cards are appended to the end of her queue in top-to-bottom order (i.e. starting from the top card of the removed substack and then following the order as they appeared in the pile).
3. If after this move the current player has no cards in hand, then the current player loses and the other wins.

Player J is a beginner and always acts according to a fixed strategy. His initial \(n\) cards are arranged in a queue in a given order; on his turn, he always removes the card at the front of the queue and places it on the pile (following the rules above). Player I, having peeped at J's strategy and the exact order in J's queue, now wishes not only to win but also to win in as few moves as possible. However, being a beginner, he needs your help for determining an optimal strategy.

Your task is to help player I by computing the minimum number of moves (i.e. turns taken by either player) needed for him to force a win, assuming both players follow the rules described. If there is no winning strategy for player I, output -1.

Notes:

• The moves count all turns (i.e. both players’ actions count as one move each).
• In the card removal procedure, when a player places a card \(x\) on top of the pile, search the pile from the second‐to‐top downward for the first occurrence of \(x\). If found at position \(i\) (with the top card at position \(\ell-1\)), remove the substack \(pile[i], pile[i+1], \dots, pile[\ell-1]\) and add these cards to the current player’s hand (for player J, they are appended to the end of her queue in top-to-bottom order).
• Player I can choose arbitrarily which card from his hand to play, whereas player J always plays the card at the front of her queue.

inputFormat

The first line contains a single integer \(n\) \((1 \le n \le 10)\), representing the number of cards initially held by each player. The second line contains \(n\) integers, representing the order of cards in player J's queue (from front to rear). It is guaranteed that for every integer \(1 \le i \le n\) there are exactly two cards with value \(i\) in the total deck.

outputFormat

Output a single integer: the minimum number of moves (i.e. turns) required for player I to force a win. If no winning strategy exists, output -1.

sample

2
1 2

8