← 返回题目列表

AtCoder · wupc2019_g

G. 定食

中文机器翻译题面 查看原题

配点 : \(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