Destiny

Interview

Time limit1sMemory limit1024 MB

Summary

Count the left-right sock pairs whose colors differ, given X left socks, X right socks, and K possible colors.

Level: Easy3 of 10
Topics: Array, Math
Solved: No attempts yet

Problem

Dongwon has $2X$ socks. Socks $1$ through $X$ are for the left foot, and socks $X+1$ through $2X$ are for the right foot.

There are $K$ sock colors, called color $1$ , color $2$ , $\cdots$ , color $K$ . The color of the $i$ -th sock is color $A_i$ .

Dongwon wants to wear one left sock and one right sock. The two socks must have different colors. How many ways can Dongwon put on socks this way?

Input

The first line contains $X$ and $K$ , separated by a space.

The second line contains $2X$ integers $A_1, A_2, \cdots, A_{2X}$ , separated by spaces.

Output

Print the number of ways Dongwon can put on a left sock and a right sock so that their colors differ. The answer can exceed the range of a 32-bit integer.

Constraints

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

Examples4

Example 1
Input
```
4 5
1 3 2 4 3 1 1 5
```
Expected output
```
13
```
Example 2
Input
```
5 2
1 2 2 1 2 1 1 1 1 2
```
Expected output
```
14
```
Example 3
Input
```
5 3
1 1 1 1 1 3 3 3 3 3
```
Expected output
```
25
```
Example 4
Input
```
5 3
2 2 2 2 2 2 2 2 2 2
```
Expected output
```
0
```