[Baltic2006]RLE COMPRESSION

有一种简单的游程压缩方式，可以表示连续出现的相同字符。例如，$\texttt{aaaaa}$ 可以压缩为 $\texttt{\#a5}$，其中 $\texttt{\#}$ 表示其后的内容采用压缩形式，$\texttt{a}$ 是重复字符，$5$ 是重复次数。

在本题中，字符集由 $0$ 到 $n-1$ 的整数表示，特殊标记 $\texttt{\#}$ 也由其中一个整数表示。初始时，使用 $0$ 表示特殊标记，但表示特殊标记的整数可以在压缩过程中改变。编码中的重复次数同样使用 $0$ 到 $n-1$ 的整数表示。因此，一个整数数列经过压缩后，仍是一个仅包含 $0$ 到 $n-1$ 的整数数列。

设当前用于表示特殊标记的整数为 $e$，压缩规则如下：

1. 除 $e$ 以外的所有整数均直接表示原数列中的对应字符。
2. 当读到 $e$ 时，根据其后两个整数进行解释：
   • 若其后为 $e,k$，则表示字符 $e$ 连续出现 $k+1$ 次；
   • 若其后为 $b,0$，其中 $b\ne e$，则将此后用于表示特殊标记的整数改为 $b$；
   • 若其后为 $b,k$，其中 $b\ne e$ 且 $k>0$，则表示字符 $b$ 连续出现 $k+3$ 次。

例如，当 $n=4$ 时，原数列为 $\texttt{1002222223333303020000}$，它的一种压缩表示为 $\texttt{10010230320100302101}$。

给定一个压缩后的数列，请求出能够表示同一原数列的最短压缩数列的长度。

输入格式

第一行包含一个整数 $n$，表示字符集的大小。

第二行包含一个整数 $m$，表示给定压缩数列的长度。

第三行包含 $m$ 个整数，每个整数均在 $0$ 到 $n-1$ 之间，表示给定的压缩数列。

输出格式

输出一个整数，表示能够还原出同一原数列的最短压缩数列的长度。

样例输入

样例 $1$：

4
20
1 0 0 1 0 2 3 0 3 2 0 1 0 0 3 0 2 1 0 1

样例 $2$：

14
15
10 10 10 0 10 0 10 10 13 10 10 13 10 10 13

样例输出

样例 $1$：

19

样例 $2$：

9

数据范围

• $2\le n\le 10^5$；
• $1\le m\le 2\times 10^6$；
• 压缩数列中的每个整数均在 $0$ 到 $n-1$ 之间。

来源与许可

本题为 Baltic 2006 试题「RLE COMPRESSION」，题面与测试数据整理自 BZOJ。

样例 1

输入

4
20
1 0 0 1 0 2 3 0 3 2 0 1 0 0 3 0 2 1 0 1

输出

19

样例 2

输入

14
15
10 10 10 0 10 0 10 10 13 10 10 13 10 10 13

输出

9