Informatica Online Judge

  Why Did the Cow Cross the Road 2 [2335 / 091F]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 13   Total Tried : 17


The Champion of this Problem (C++) : gs17044 - ms / 991byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

농부 존의 농장은 대형 원형 목초지를 가지고 있어서, 존의 소는 매일 아침 이 원형 목초지에 들어 가서 풀을 먹고, 저녁에 다시 목초지를 나와서 헛간으로 돌아온다.

소는 습관의 동물로, 매일 같은 길로 길을 건넌다.
각 소는 정해진 점을 지나 들판을 횡단하고, 다른 점을 가로질러 돌아온다.

어떤 두 소도 길 위의 같은 점을 지나가지는 않는다.

소를 1부터 N마리라고 번호를 붙이고, 존은 2N개의 점을 시계방향으로 보면서 각 점을 어떤 소가 지나가는지 기록했다. 이렇게 만들어 낸 길이 2N의 수열에는 각 번호가 두 번씩 나타날 것이다.

어떤 두 소는 어떤 방법으로 걷든 그 경로가 어딘가에서 만나야 될 수도 있다. 그런 소가 총 몇 쌍인지 구해 보자.

Input

첫번째 줄에는 소의 수를 입력한다. ( $1 <= N <= 50,000$ )

두번째 줄부터는 한줄에 하나씩 길위의 점을 지나간 소의 번호를 입력한다.

Output

경로가 무조건 만나는 소가 몇 쌍인지 출력한다.

IO Example

<입력 예>
4
3
2
4
4
1
3
2
1

<출력 예>
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]