#P1017. 电影院三连座

电影院三连座

题目描述

周末到了,小兰和同学们准备一起去看电影。

电影院里有一排座位,每个座位都有一个编号。现在售票系统给出了一些还空着的座位编号,小兰想知道:一共有多少种位置,可以让三位同学坐在编号连续的三个座位上。

也就是说,如果编号为 xxx+1x+1x+2x+2 的三个座位都还空着,那么这就是一种“三连座”。

请你统计空座中一共有多少种三连座。

输入格式

第一行输入一个整数 nn,表示空座数量。

第二行输入 nn 个互不相同的整数 aia_i,表示空座的编号。

输出格式

输出一个整数,表示三连座的数量。

样例输入

7
10 12 11 15 14 13 20

样例输出

4

样例解释

空座编号排序后为:

10 11 12 13 14 15 20

其中可以组成三连座的位置有:

10 11 12
11 12 13
12 13 14
13 14 15

所以答案为 44

数据范围

对于所有测试数据,满足:

  • 3n2000003 \le n \le 200000
  • 0ai10000000000 \le a_i \le 1000000000
  • 所有 aia_i 互不相同