QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[0]

# 1913. Non-Decreasing Subsequences

Statistics

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 (1N5104) consisting solely of integers in the range 1K (1K20). You are given Q (1Q2105) queries of the form [Li,Ri] (1LiRiN). For each query, compute the number of non-decreasing subsequences of ALi,ALi+1,ARi mod 109+7.

A non-decreasing subsequence of AL,,AR is a collection of indices (j1,j2,,jx) such that Lj1<j2<<jxR and Aj1Aj2Ajx. Make sure to consider the empty subsequence!

Scoring

  • Test cases 2-3 satisfy N1000.
  • Test cases 4-6 satisfy K5.
  • Test cases 7-9 satisfy Q105.
  • Test cases 10-12 satisfy no additional constraints.

Input Format

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.

Output Format

For each query [Li,Ri], you should print the number of non-decreasing subsequences of ALi,ALi+1,ARi mod 109+7 on a new line.

Sample Input

5 2
1 2 1 1 2
3
2 3
4 5
1 5

Sample Output

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.

For the second query, the non-decreasing subsequences are (), (4), (5), and (4,5).

Problem credits: Benjamin Qi