不等子序列(Unequal Subsequences)

题目描述

给定一个数列 a₁,a₂,⋯,aₙ，请统计有多少个不相等的最长严格上升子序列。所谓两个序列不相等，就是这两个序列至少有一个对应的数字不相等。

例如对于 1,2,3,1,2,3，最长严格上升子序列是 1,2,3，尽管有多个不同的 1，但它们都是相等的。

由于答案可能很大，输出答案模 1,000,000,007 的余数。

输入格式

第一行：单个整数 n； 第二行：n 个整数 a₁,a₂,⋯,aₙ。

输出格式

单个整数：表示不相等的最长严格上升子序列的数量模 1,000,000,007 的余数。

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 100；
• 对于 60% 的数据，1 ≤ n ≤ 2000；
• 对于 100% 的数据，1 ≤ n ≤ 100,000，
• 1 ≤ aᵢ ≤ n。

样例输入 #1

6 1 2 3 1 2 3

样例输出 #1

1

样例输入 #2

6 2 1 4 3 6 5

样例输出 #2

8

说明：第一项可以选1或2，第二项可以选3或4，第三项可以选5或6

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐。

测试点分布