CF1147A Hide and Seek

Alice 和 Bob 在一条有 $n$ 个格子的直线上玩游戏。这些格子从 $1$ 到 $n$ 编号。对于每个 $i$，$1 \leq i \leq n-1$，格子 $i$ 和格子 $i+1$ 是相邻的。 Alice 最初在某个格子上放有一个棋子，Bob 试图猜测它的位置。 Bob 依次猜测一系列格子编号 $x_1, x_2, \ldots, x_k$。在第 $i$ 次提问时，Bob 问 Alice 她的棋子是否在格子 $x_i$ 上。也就是说，Alice 对于 Bob 的每个问题都可以回答“YES”或“NO”。 在整个过程中，Alice 最多可以有一次机会，在回答某个问题之前或之后，将她的棋子从当前格子移动到一个相邻的格子。Alice 会采取某种方式，使得她能够对 Bob 的所有问题都回答“NO”。 注意，Alice 可以选择在回答第一个问题之前或最后一个问题之后移动棋子，也可以选择完全不移动。 给定 $n$ 和 Bob 的问题序列 $x_1, \ldots, x_k$，你需要计算有多少种方案能让 Alice 对所有问题都回答“NO”。 用 $(a, b)$ 表示一种方案，表示 Alice 从格子 $a$ 开始，最终停在格子 $b$。如果 $(a_i, b_i)$ 和 $(a_j, b_j)$ 满足 $a_i \neq a_j$ 或 $b_i \neq b_j$，则认为它们是不同的方案。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 10^5$），分别表示格子的数量和 Bob 提问的次数。 第二行包含 $k$ 个整数 $x_1, x_2, \ldots, x_k$（$1 \leq x_i \leq n$），表示 Bob 的每次提问。

输出一个整数，表示能让 Alice 对所有问题都回答“NO”的方案数。

记 $(i, j)$ 表示 Alice 从格子 $i$ 开始，最终停在格子 $j$ 的一种方案。 在第一个样例中，合法的方案有 $(1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3), (3, 4), (4, 3), (4, 5)$。例如，$(3,4)$ 是合法的，因为 Alice 可以从格子 $3$ 开始，在前三次提问时都不移动，最后一次提问后移动到格子 $4$。 $(4,5)$ 也是合法的，因为 Alice 可以从格子 $4$ 开始，在第一次提问时不移动，然后在接下来的两次提问时移动到格子 $5$。注意，$(4,5)$ 只计数一次，尽管 Alice 可以选择在不同的提问时移动，但我们只统计每一对起始和结束位置一次。 在第二个样例中，Alice 没有合法的方案。 在最后一个样例中，所有满足 $|i-j| \leq 1$ 且不等于 $(42, 42)$ 的 $(i, j)$ 都是合法的方案。 由 ChatGPT 4.1 翻译