AIOC Banner

Problem: Snap Dragons III: Binary Snap

Want to try solving this problem? You can submit your code online if you log in or register.


Snap Dragons III: Binary Snap

Input File: snapin.txt
Output File: snapout.txt
Time Limit: 1 second

Have you ever heard of Melodramia, my friend? It is a land of forbidden forests and boundless swamps, of sprinting heroes and dashing heroines. And it is home to two dragons, Rose and Scarlet, who, despite their competitive streak, are the best of friends.

Rose and Scarlet love playing Binary Snap, a game for two players. The game is played with a deck of cards, each with a numeric label from 1 to N. There are two cards with each possible label, making 2N cards in total. The game goes as follows:

After many millenia of playing, the dragons noticed that having more possible Dragon Pairs would often lead to a more exciting game. It is for this reason they have summoned you, the village computermancer, to write a program that reads in the order of cards in the shuffled deck and outputs the maximum number of Dragon Pairs that the dragons can find.

Input

The first line of input will contain a single integer, N. The following 2N lines will each contain an integer, vi (where 1 ≤ viN), representing the label of the ith card from the top of the shuffled deck.

Output

Output should consist of a single integer: the maximum number of Dragon Pairs Scarlet can deal in a game of Binary Snap with the deck in the given order.

Sample Input

4
1
4
1
2
3
2
3
4

Sample Output

3

Explanation

We can make Dragon Pairs from all of the cards except the 4s with the following sequence of moves:

This gives us 3 Dragon Pairs in total, so we must output 3.

Subtasks & Constraints

For all subtasks, 1 ≤ N ≤ 100  000.

 


Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024,  1:00am AEDT