【入门题】暴力拿分法1

• IOI赛制

IOI赛制介绍

我们目前的碰到几乎所有大厂笔试，所使用的都是IOI赛制。通俗来讲，该赛制允许进行无数次提交，按最高分计算。每次提交后台有n组测试样例(一组样例由一个输入数据和一个输出数据组成)，我们所得的分数为$\frac{正确的组数}{n}*100\%$。也就是说我们允许使用非标准解法拿部分分

IOI赛制中的常见技巧-暴力拿(骗)分法

一种最常见的技巧是：碰到想不出满分最优解的题目，我们可以迅速的用暴力写完拿完部分分(部分情况下可达70%)，把时间留给我们会的题目。我们本道题目是来自24年字节跳动9.25机考最后一道题目，是一道较困难的，数据结构优化的动态规划题目。

题目内容

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

严格单调递减序列是指一个序列满足：长度为$1$或从第$2$项开始，每一项均小于前一项的序列。

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

输入描述

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

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

输出描述

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

样例1

输入

4
1 3 5 2

输出

6

说明

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