题解

题面描述

给定一个长度为 $n$ 的整数数组 $a$，我们称一个长度为 $5$ 的数组是“顺子”，当且仅当将该数组排序后，每个元素都比前一个恰好大 $1$。
例如，$[4,6,3,2,5]$ 排序后为 $[2,3,4,5,6]$ ，满足条件；而 $[1,4,1,5,3]$ 排序后为 $[1,1,3,4,5]$ ，不满足条件。
现在要统计原数组中有多少个长度为 $5$ 的子序列（保持原序但可删去若干元素）是一个“顺子”，结果对 $10^{9}+7$ 取模。

思路

题目内容

小红定义一个数组是 “顺子”，当且仅当若将该数组排序，每个元素均比其前一个元素恰好大 $1$。例如，$[4,6,3,2,5]$ 是顺子，而 $[1,4,1,5,3]$ 则不是顺子。

现在小红拿到了一个数组，她想知道有多少长度为 $5$ 的子序列为一个 “顺子"？由于答案可能过大，请对 $10^9+7$ 取模。

定义数组的子序列为:数组删除若干个元素形成的新数组。

输入描述

第一行输入一个正整数 $n(1\leq n\leq 10^5)$，代表数组的长度。

第二行输入 $n$ 个正整数 $a_i(1\leq a_i\leq 10^9)$，代表数组的元素。

输出描述

一个整数，代表顺子的数量对 $10^9 + 7$ 取模的值。

示例1

输入

6
1 2 3 4 5 6

输出

2

示例2

输入

10
1 2 3 4 5 1 2 3 4 5

输出

32