P6842 [BalkanOI 2009] Strip

[英文题面](/problem/U126974) | [题目来源](http://www.cs.org.mk/boi2009/tasks.html)

让我们考虑一条宽度为 $1$、长度为 $n$、厚度为可忽略的条带，由单位正方形组成。如图所示（其中 $n=7$），从它的左边开始，我们使用从 $0$ 到 $n$ 的非负整数命名每个垂直的线。我们只能沿着这些垂直线折叠长方形条带，并且在这之后两个部分被粘在一起，不再会被拉直。  自然地，在折叠之后，一些编号会重叠在一起，形成一个有更多编号的垂直线。图中显示了沿垂直线 $3$ 折叠后的情况。在此操作之后，有一些线会有两个编号。例如，我们同样可以说 $1$ 或 $5$，他们代表的是同一条垂直线。再沿着 $2$ 折叠（我们也可以说 $4$，都是一样的），就会有一条垂直线有甚至三个名称，正如我们所看到的：$(1;3;5)$。举个例子，如果我们沿着段 $3$ 对长方形条带进行折叠，我们只需旋转条带，而不改变其名称或长度。我们把这样的折叠称为“空的”：它**不是**非法的，只是没有做任何重大的改变。 按照这种方式，一组长度为 $k$ 的整数数列（每个整数从 $0$ 到 $n$）唯一地定义了条带的折叠方法。编写一个程序，找出折叠完成后该条带的长度。

从标准输入读入。 - 第一行两个正整数 $n,k$，表示条带长度和折叠次数。 - 第二行 $k$ 个非负整数，表示折叠的顺序，每个数都在 $\left[0,n\right]$ 的范围内。

输出到标准输出。 一行，一个整数，表示折叠后的长度。

**数据范围** $n$ 有不超过 $18$ 个整数位，$k\le 10000$。 --- **样例 $2$ 解释** 折叠步骤如图： 初始情况：$\{0\,1\,2\,3\,4\,5\,6\,7\,8\,9\}$。 折叠步骤：$\rightarrow \{0\,(1;9)\,(2;8)\,(3;7)\,(4;6)\,5\}\rightarrow \{(1;9)\,(0;2;8)\,(3;7)\,(4;6)\,5\}\rightarrow \{(0;2;8)\,(1;3;7;9)\,(4;6)\,5\}\rightarrow \{(1;3;7;9)\,(0;2;4;6;8)\,5\}$。 （备注：样例 $1$ 与图片相同）