Page not loading? Try clicking here.
Placeholder

#8064

양말 1s 1024MB

Problems

정올이는 2X개의 양말을 가지고 있다.

1번째 ~ X번째 양말은 왼발에 신을 수 있는 양말이고, X+1번째 ~ 2X번째 양말은 오른발에 신을 수 있는 양말이다.

양말의 색은 총 K가지 존재하고, 각각 1번 색, 2번 색, \cdots, K번 색이라고 부른다.

i번째 양말의 색은 A_i번 색이다.

정올이는 왼발 양말 하나와 오른발 양말 하나를 신고 나가려 한다. 양쪽 발에 신는 양말의 색은 달라야 한다. 정올이가 이와 같이 양말을 신고 가는 경우의 수는?


Input

첫째 줄에 양말의 개수 X와 양말의 색의 가짓수 K가 공백을 사이에 두고 주어진다.

둘째 줄에 각 양말의 색의 번호를 나타나는 2X개의 수 A_1, A_2, \cdots, A_{2X}가 공백을 사이에 두고 주어진다.

[제약 조건]

  • 1 \le X \le 100\,000

  • 1 \le K \le 10\,000

  • 1 \le A_i \le K (1 \le i \le 2X)


Output

양쪽 발에 신는 양말의 색이 다르도록 정올이가 양말을 신고 가는 경우의 수를 출력하라. 답의 크기가 32비트 정수형의 범위를 초과할 수 있음에 유의하라.


Example #1

4 5
1 3 2 4 3 1 1 5
13

정올이는 왼발 전용 양말을 총 4개 가지고 있으며, 각 양말의 색은 1, 3, 2, 4번 색이다.

정올이는 오른발 전용 양말을 총 4개 가지고 있으며, 각 양말의 색은 3, 1, 1, 5번 색이다.

정올이가 양쪽 발에 양말을 신고 가는 경우는, (왼발 양말의 색, 오른발 양말의 색) = (1, 3), (1, 5), (3, 1), (3, 1), (3, 5), (2, 3), (2, 1), (2, 1), (2, 5), (4, 3), (4, 1), (4, 1), (4, 5)인 총 13가지 경우가 있다.


Example #2

5 3
1 1 1 1 1 3 3 3 3 3
25

Example #3

5 3
2 2 2 2 2 2 2 2 2 2
0


Source

연세대학교 미래캠퍼스 강원도 대학생 코딩 경진대회 B번
You must sign in to write code.