#LUOGUP8120. [语言月赛202301] 避雷针

    ID: 1396 远端评测题 1000ms 512MiB 尝试: 5 已通过: 4 难度: 10 上传者: 标签>2023O2优化循环结构数组语言月赛

[语言月赛202301] 避雷针

题目描述

nn 个避雷针从左至右排成一排,我们将它们从左至右依次标号为 1n1 \sim n

现在有 mm 道雷依次劈下。你得知了一串序列 a1,,ama _ 1, \cdots, a _ m。对于第 ii 道雷,其劈中了 ai2a _ i - 2(如果存在)、ai1a _ i - 1(如果存在)、aia _ iai+1a _ i + 1(如果存在)、ai+2a _ i + 2(如果存在)号避雷针。

mm 道雷劈完后,你想要知道,被劈过至少一次的避雷针有几个。

输入格式

输入共两行。

第一行为两个整数 n,mn, m,代表避雷针数量和雷的数量。

第二行为 mm 个整数 a1,,ama _ 1, \cdots, a _ m,代表题面中的序列。

输出格式

输出共一行。

输出一行一个整数,被劈过至少一次的避雷针的数量。

17 1
4
5
10 1
2
4
9 3
3 7 7
9

提示

样例 1 解释

被劈中的避雷针是 2,3,4,5,62, 3, 4, 5, 6 号,共 55 个。

样例 2 解释

被劈中的避雷针是 1,2,3,41, 2, 3, 4 号,共 44 个。请注意 a12=0a _ 1 - 2 = 0 号避雷针不存在,也不应被劈中。

样例 3 解释

被劈中的避雷针是 1,2,3,4,5,6,7,8,91, 2, 3, 4, 5, 6, 7, 8, 9 号,共 99 个。

请注意尽管部分避雷针被劈了两次甚至三次,对这些避雷针我们仍然只计数一次。

数据规模与约定

  • 对于前 10%10\% 的数据,保证 n=1n = 1
  • 对于前 30%30\% 的数据,保证 m=1m = 1
  • 对于另外 20%20\% 的数据,保证 mn2m \leq n - 2i[1,m],ai=i\forall i \in [1, m], a _ i = i
  • 对于 100%100\% 的数据,保证 1n,m1061 \leq n,m \leq 10 ^ 61ain1 \leq a _ i \leq n