配点 : \(200\) 点
問題文
W大学食堂提供\(N\)种套餐,每种套餐都用整数\(0,1,\cdots,{N-1}\)表示。
目前食堂有\(M\)人在排队等候。数列\(A\)表示谁点了哪份套餐,队列前面第\(i\)个人点的套餐是\(A_i\)。
食堂为了提高工作效率,一次只准备一种套餐,并为所有排队点餐同种套餐的人员提供该套餐。此时,如果给尚未提供套餐的人\(i\)提供套餐给他后面排队的人\(j\ (i < j < M)\),则每增加一个\(j\),该人\(i\)的不满意度就会增加1。
在自助餐厅,在 \(N!\) 种提供套餐的方式中,我希望以最小化当前排队的 \(M\) 人总不满意程度的顺序提供餐点。请输出套餐按适当顺序上菜时的总不满意程度。
制約
- \(1 \leq N \leq 15\)
- \(1 \leq M \leq 200000\)
- \(0 \leq A_i \leq N-1\)
- 输入的值全部都是整数。
入力
输入将以以下形式从标准输入给出。
\(N\) \(M\)
\(A_0\) \(A_1\) \(\dots\) \(A_{M-1}\)
出力
请输出按适当顺序提供套餐时\(M\)人总不满意程度的最小值。
入力例 1
2 5 0 1 0 0 1
出力例 1
2
- 如果先上套餐\(0\),则第\(2\)人的不满意度会增加\(2\),而第\(5\)人的不满意度不会增加,所以总的不满意度为\(2\)。
- 如果先上套餐\(1\),则第\(1\)人的不满意度会增加\(2\),第\(3\)人和\(4\)人的不满意度会分别增加\(1\),所以总的不满意度会是\(4\)。
因此,通过先提供套餐\(0\),然后提供套餐\(1\),可以将不满意的总量降到最低。
入力例 2
5 5 4 1 2 3 0
出力例 2
0