← 返回题目列表

Codeforces · 1147/A

A. 捉迷藏

中文机器翻译题面 查看原题

Alice 和 Bob 正在用 $$$n$$$ 单元格在线玩游戏。有 $$$n$$$ 单元格标记为从 $$$1$$$ 到 $$$n$$$。对于从 $$$1$$$ 到 $$$n-1$$$ 的每个 $$$i$$$,单元格 $$$i$$$ 和 $$$i+1$$$ 是相邻的。

Alice 最初在线路上的某个单元格上有一个令牌,Bob 尝试猜测它在哪里。

Bob 按顺序猜测一系列行单元号 $$$x_1, x_2, \ldots, x_k$$$。在第 $$$i$$$ 问题中,Bob 询问 Alice 她的令牌当前是否位于单元格 $$$x_i$$$ 上。也就是说,Alice 可以对每个 Bob 的问题回答“是”或“否”。

在此过程中最多一次,在回答问题之前或之后,Alice 被允许将她的令牌从当前单元格移动到某个相邻单元格。爱丽丝的行为方式使得她能够对鲍勃的所有问题回答“否”。

请注意,Alice 甚至可以在回答第一个问题之前或回答最后一个问题之后移动她的令牌。 Alice 也可以选择根本不动。

给你 $$$n$$$ 和 Bob 的问题 $$$x_1, \ldots, x_k$$$。您想要计算让 Alice 对 Bob 的所有问题都回答“否”的场景数量。

让 $$$(a,b)$$$ 表示这样一个场景:Alice 从单元格 $$$a$$$ 开始,到单元格 $$$b$$$ 结束。如果 $$$a_i \neq a_j$$$ 或 $$$b_i \neq b_j$$$,则两种情况 $$$(a_i, b_i)$$$ 和 $$$(a_j, 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 对 Bob 的所有问题回答“否”的场景数量。

示例

输入 #1

5 3
5 1 4

输出 #1

9

输入 #2

4 8
1 2 3 4 4 3 2 1

输出 #2

0

输入 #3

100000 1
42

输出 #3

299997

注意

符号 $$$(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)$$$ 其中 $$$|i-j| \leq 1$$$ 除了 $$$(42, 42)$$$ 都是有效的场景。