NC222459. [USACOJan20P]Non-DecreasingSubsequences
描述
Bessie was recently taking a USACO contest and encountered the following problem. Of course, Bessie knows how to solve it. But do you?
Consider a sequence A1,A2,…,AN of length N (1≤N≤5⋅104) consisting solely of integers in the range 1…K (1≤K≤20). You are given Q (1≤Q≤2⋅105) queries of the form [Li,Ri] 1≤Li≤Ri≤N). For each query, compute the number of non-decreasing subsequences of 
,
…,
mod 109+7.
A non-decreasing subsequence of AL,…,AR is a collection of indices (j1,j2,…,jx) such that L≤j1<j2<⋯<jx≤R and 
≤
≤⋯≤
. Make sure to consider the empty subsequence!
输入描述
The first line contains two space-separated integers N and K.
The second line contains N space-separated integers A1,A2,…,AN.
The third line contains a single integer Q.
The next Q lines each contain two space-separated integers Li and Ri.
输出描述
For each query [Li,Ri], you should print the number of non-decreasing subsequences of
示例1
输入:
5 2 1 2 1 1 2 3 2 3 4 5 1 5
输出:
3 4 20
说明:
For the first query, the non-decreasing subsequences are (),(2), and (3). (2,3) is not a non-decreasing subsequence because A2≰A3.For the second query, the non-decreasing subsequences are (), (4), (5), and (4,5).