Reimu and Marisa are playing a card game, described as follows:
There are $$$2n$$$ cards in total, with numbers $$$1$$$ to $$$n$$$ each appearing twice. Each player holds $$$n$$$ cards. They take turns playing one card, with Reimu going first.
After a player plays a card, if there are at least $$$2$$$ cards in the pile, and the top card of the pile is the same as the bottom card of the pile, then that player takes all the cards from the pile and gets one point.
Now, given Reimu's card sequence, Marisa wants to minimize Reimu's score. Under optimal strategy, what is the minimum score Reimu can get?
First line: a positive integer $$$n\ (1\le n\le 10^5)$$$.
Second line: $$$n$$$ positive integers $$$a_i\ (1\le a_i\le n)$$$, with the guarantee that the same $$$a_i$$$ appears at most twice.
First line: a positive integer, indicating Reimu's minimum score.
Next line: $$$n$$$ positive integers $$$b_i$$$, such that the multiset $$$[a_1, ..., a_n, b_1, ..., b_n]$$$ contains each number from $$$1$$$ to $$$n$$$ exactly twice.
This represents while the card sequence is $$$[a_1, b_1, a_2, b_2, ..., a_n, b_n]$$$, Reimu's score is exactly the minimum.
If there are multiple answers, output any one of them.
3 1 2 3
0 2 3 1
4 1 2 1 4
1 2 4 3 3
Example 1:
The card sequence is $$$[1,2,2,3,3,1]$$$. Marisa gets $$$1$$$ point after the last $$$1$$$, Reimu gets $$$0$$$ points. So $$$0$$$ points is the minimum score.
Example 2: The card sequence is $$$[1,2,2,4,1,3,4,3]$$$. Reimu gets $$$1$$$ point after the second $$$1$$$, then Marisa gets $$$1$$$ point after the last $$$3$$$.
It is proved that there is no solution in which Reimu gets $$$0$$$ points, so $$$1$$$ point is the minimum score.
