CF1236E Alice and the Unfair Game

Alice 正在和她的好朋友 Marisa 玩一个游戏。 有 $n$ 个盒子排成一行，从左到右编号为 $1$ 到 $n$。Marisa 会把一个娃娃藏在其中一个盒子里。然后 Alice 有 $m$ 次机会猜测娃娃所在的盒子编号。如果 Alice 能正确猜中娃娃当前所在的盒子编号，她就赢得游戏，否则她的朋友就会赢得游戏。 为了获胜，Marisa 会使用一些不公平的技巧。在每次 Alice 猜测之后，她可以把娃娃移动到相邻的盒子，或者保持不动。对于所有 $1 \leq i \leq n-1$，盒子 $i$ 和 $i+1$ 被认为是相邻的。在游戏开始前，她也可以使用一次这个技巧。 因此，游戏的流程如下：游戏开始，Marisa 先使用一次技巧，Alice 进行第一次猜测，Marisa 再次使用技巧，Alice 进行第二次猜测，Marisa 再次使用技巧，……，Alice 进行第 $m$ 次猜测，Marisa 再次使用技巧，游戏结束。 Alice 想好了一个序列 $a_1, a_2, \ldots, a_m$。在第 $i$ 次猜测时，她会询问娃娃是否在第 $a_i$ 个盒子里。她想知道有多少种方案 $(x, y)$（对于所有 $1 \leq x, y \leq n$），使得如果 Marisa 一开始把娃娃放在第 $x$ 个盒子里，并且在游戏结束时娃娃在第 $y$ 个盒子里，Marisa 能通过她的技巧获胜。请你帮她计算这样的方案数。

第一行包含两个整数 $n$ 和 $m$，用空格分隔（$1 \leq n, m \leq 10^5$），表示盒子的数量和 Alice 的猜测次数。 第二行包含 $m$ 个整数 $a_1, a_2, \ldots, a_m$，用空格分隔（$1 \leq a_i \leq n$），其中 $a_i$ 表示 Alice 第 $i$ 次猜测的盒子编号。

输出一个整数，表示满足条件的方案数，即所有满足条件的盒子对 $(x, y)$ 的数量（$1 \leq x, y \leq n$）。

在第一个样例中，可能的方案有 $(1, 1)$、$(1, 2)$、$(2, 1)$、$(2, 2)$、$(2, 3)$、$(3, 2)$、$(3, 3)$。 以 $(2, 2)$ 为例，游戏过程中娃娃所在的盒子可以是 $2 \to 3 \to 3 \to 3 \to 2$。 由 ChatGPT 4.1 翻译