AT_wupc2019_g.Teishoku

在 W 大学的食堂里，有 \(N\) 种套餐可供选择，这些套餐用整数 \(0, 1, \cdots, N-1\) 标识。

此时，食堂外已经有 \(M\) 个人在排队，等待他们所点的套餐。每个人选择的套餐用序列 \(A\) 表示，其中第 \(i\) 位顾客点的套餐为 \(A_i\)。

为提高工作效率，食堂采取的做法是每次只制作一种套餐，并将其直接提供给所有点了这种套餐且还排在队列中的顾客。在这样的安排中，对于尚未获得套餐的顾客 \(i\)，如果他的后面有顾客 \(j\ (i < j)\) 也选择了相同的套餐，那么 \(i\) 的不满意度将增加 \(1\)。

食堂希望找出一种最佳的套餐制作与供应顺序，以使得所有顾客的不满意度总和达到最小。请计算并输出这种最优顺序下的不满意度总和。

输入为标准输入，格式如下：

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

在最佳的套餐提供顺序下，输出所有顾客的不满意度总和的最小值。

• (1 \leq N \leq 15)
• (1 \leq M \leq 200000)
• (0 \leq A_i \leq N-1)
• 所有输入数值均为整数。

示例解释 1

• 如果优先制作并提供套餐 (0)，则第 (2) 位顾客的不满意度会上升 (2)，而第 (5) 位顾客的不满意度不变，总的不满意度因此为 (2)。
• 如果优先制作并提供套餐 (1)，则第 (1) 位顾客的不满意度会上升 (2)，第 (3) 和第 (4) 位顾客的不满意度各增加 (1)，总的不满意度达到 (4)。

因此，通过先提供套餐 (0) 然后提供套餐 (1)，能够最小化不满意度的总和。

本翻译由 AI 自动生成