/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 150 点
問題文
2N 人の人が横一列に並んでおり、左から i 番目の人は色 A_i の服を着ています。ここで、服の色は 1 から N の N 色であり、それぞれの色についてちょうど 2 人の人がその色の服を着ています。
i=1,2,\ldots,N のうち、以下の条件を満たすものは何通りあるか求めてください。
- 色 i の服を着た二人の人の間にはちょうど一人いる。
制約
- 2\leq N\leq 100
- 1\leq A_i \leq N
- A には 1 以上 N 以下の整数全てがそれぞれ 2 個ずつ含まれる
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{2N}
出力
答えを出力せよ。
入力例 1
3 1 2 1 3 2 3
出力例 1
2
条件を満たす i は 1 と 3 の 2 個です。
実際、色 1 の服を着ているのは左から 1 番目の人と左から 3 番目の人で、間にちょうど一人います。
入力例 2
2 1 1 2 2
出力例 2
0
条件を満たす i が存在しない場合もあります。
入力例 3
4 4 3 2 3 2 1 4 1
出力例 3
3
Score : 150 points
Problem Statement
There are 2N people standing in a row, and the person at the i-th position from the left is wearing clothes of color A_i. Here, the clothes have N colors from 1 to N, and exactly two people are wearing clothes of each color.
Find how many of the integers i=1,2,\ldots,N satisfy the following condition:
- There is exactly one person between the two people wearing clothes of color i.
Constraints
- 2 \leq N \leq 100
- 1 \leq A_i \leq N
- Each integer from 1 through N appears exactly twice in A.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_{2N}
Output
Print the answer.
Sample Input 1
3 1 2 1 3 2 3
Sample Output 1
2
There are two values of i that satisfy the condition: 1 and 3.
In fact, the people wearing clothes of color 1 are at the 1st and 3rd positions from the left, with exactly one person in between.
Sample Input 2
2 1 1 2 2
Sample Output 2
0
There may be no i that satisfies the condition.
Sample Input 3
4 4 3 2 3 2 1 4 1
Sample Output 3
3