#P14160. 【暴力拿分法1】统计最长下降子序列

【暴力拿分法1】统计最长下降子序列

题目内容

小塔有一个长度为nn的数组a1,a2,...,ana_1,a_2,...,a_n,请你帮助他求出有多少个严格单调递减的子序列。结果可能很大,对109+710^9+7取模后在输出。

严格单调递减序列是指一个序列满足:长度为11或从第22项开始,每一项均小于前一项的序列。

由原来的序列删除(或不删除)某些元素而不改变其余元素的相对顺序的序列称为子序列。

输入描述

第一行输入一个整数 nn(1n2×1051≤n≤2×10^5)代表数组中的元素数量。

第二行输入n个整数a1,a2,...,ana_1,a_2,...,a_n(1ai1091≤a_i≤10^9)代表元素。

输出描述

在一行输出一个整数,代表严格单调递减的子序列的个数,由于数据较大,输出答案对109+710^9+7取模的结果。

样例1

输入

4
1 3 5 2

输出

说明

由两个元素构成的满足题意的子序列为{3,23,2}、{5,25,2}