시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB139956448444.080%

문제

동원이는 $2X$개의 양말을 가지고 있다. $1$번째 ~ $X$번째 양말은 왼발에 신을 수 있는 양말이고, $X+1$번째 ~ $2X$번째 양말은 오른발에 신을 수 있는 양말이다.

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

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

입력

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

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

출력

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

제한

  • $1 \le X \le 100\,000$
  • $1 \le K \le 10\,000$
  • $1 \le A_i \le K$ ($1 \le i \le 2X$)

예제 입력 1

4 5
1 3 2 4 3 1 1 5

예제 출력 1

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가지 경우가 있다.

예제 입력 2

5 2
1 2 2 1 2 1 1 1 1 2

예제 출력 2

14

예제 입력 3

5 3
1 1 1 1 1 3 3 3 3 3

예제 출력 3

25

예제 입력 4

5 3
2 2 2 2 2 2 2 2 2 2

예제 출력 4

0

출처

University > 강원도 대학생 코딩 경진대회 > 강원도 대학생 코딩 경진대회 B번