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 自动生成**