Problem Description

The cafeteria at W University offers \(N\\) types of set meals, each represented by an integer from \(0, 1, \\cdots, N-1\\).

Currently, there are \(M\\) people waiting in line. The sequence \(A\\) represents which set meal each person ordered, where the \(i\\)-th person in line from the front ordered the set meal \(A_i\\).

For efficiency, the cafeteria prepares and serves only one type of set meal at a time, providing it to all waiting people who ordered that type. For a person \(i\\) who has not yet received their set meal, the dissatisfaction of that person increases by the number of people \(j\\) (with \(i < j\\)) who are behind them in line and have already received their set meal.

The cafeteria wants to serve the set meals in one of the \(N!\\) possible orders that minimizes the total dissatisfaction of the \(M\\) people waiting. Output the minimum total dissatisfaction when set meals are served in the optimal order.

Input Format

The input is given from the standard input in the following format:

\(N\) \(M\)
\(A_0\) \(A_1\) \(\dots\) \(A_{M-1}\)

Output Format

Output the minimum total dissatisfaction of the \(M\\) people when set meals are served in the optimal order.

Sample Input and Output

Sample Input #1

2 5
0 1 0 0 1

Sample Output #1

2

Sample Input #2

5 5
4 1 2 3 0

Sample Output #2

0

Notes/Hints

Constraints

• \(1 \\leq N \\leq 15\\)
• \(1 \\leq M \\leq 200000\\)
• \(0 \\leq A_i \\leq N-1\\)
• All input values are integers.

Sample Explanation 1

• If set meal \(0\\) is served first, the dissatisfaction of the 2nd person increases by \(2\\), while the 5th person's dissatisfaction does not increase, resulting in a total dissatisfaction of \(2\\).
• If set meal \(1\\) is served first, the dissatisfaction of the 1st person increases by \(2\\), and the dissatisfaction of the 3rd and 4th persons each increases by \(1\\), resulting in a total dissatisfaction of \(4\\).

Therefore, serving set meal \(0\\) first and then set meal \(1\\) minimizes the total dissatisfaction.

见题面 Input 部分

见题面 Output 部分