問題文

W大学の食堂では\(N\)種類の定食を提供しており、各定食は\(0,1, \cdots ,{N-1}\)の整数で表されます。

今、食堂には\(M\)人が順番待ちで並んでいます。誰がどの定食を頼んだかは数列\(A\)で表され、順番待ちの前から\(i\)番目の人が頼んだ定食は\(A_i\)です。

食堂では効率化のため、同時に1種類の定食のみを作り、同じ種類の定食を頼んだ順番待ちの人全員に定食を提供します。この時、まだ定食の提供されていない人 \(i\)について、その人よりも後ろに並んでいる人 \(j\ (i < j < M)\) に定食が提供された場合、人 \(i\) の不満度は人 \(j\) ひとりにつき 1 だけ上昇します。

食堂では\(N!\)通りある定食の提供手順のうち、今並んでいる\(M\)人の不満度の総和が最小になるような順序で定食を提供したいです。適切な順序で定食を提供した時の不満度の総和を出力してください。

制約

• \(1 \leq N \leq 15\)
• \(1 \leq M \leq 200000\)
• \(0 \leq A_i \leq N-1\)
• 入力される値はすべて整数である。

入力例 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