Weighted Increasing Subsequences solution codeforces

Weighted Increasing Subsequences solution codeforces

 

You are given the sequence of integers a1,a2,,ana1,a2,…,an of length nn.

The sequence of indices i1<i2<<iki1<i2<…<ik of length kk denotes the subsequence ai1,ai2,,aikai1,ai2,…,aik of length kk of sequence aa.

The subsequence ai1,ai2,,aikai1,ai2,…,aik of length kk of sequence aa is called increasing subsequence if aij<aij+1aij<aij+1 for each 1j<k1≤j<k.

The weight of the increasing subsequence ai1,ai2,,aikai1,ai2,…,aik of length kk of sequence aa is the number of 1jk1≤j≤k, such that exists index ik<xnik<x≤n and ax>aijax>aij.

For example, if a=[6,4,8,6,5]a=[6,4,8,6,5], then the sequence of indices i=[2,4]i=[2,4] denotes increasing subsequence [4,6][4,6] of sequence aa. The weight of this increasing subsequence is 11, because for j=1j=1 exists x=5x=5 and a5=5>ai1=4a5=5>ai1=4, but for j=2j=2 such xx doesn’t exist. Weighted Increasing Subsequences solution codeforces

Find the sum of weights of all increasing subsequences of aa modulo 109+7109+7.

Input

The first line contains a single integer tt (1t10001≤t≤1000) — the number of test cases.

The first line of each test case contains the single integer nn (1n21051≤n≤2⋅105) — the length of the sequence aa.

The second line of each test case contains nn integers a1,a2,,ana1,a2,…,an (1ai1091≤ai≤109) — the sequence aa.

It is guaranteed that the sum of nn over all test cases doesn’t exceed 21052⋅105.

Output Weighted Increasing Subsequences solution codeforces

For each test case, print the sum of weights of all increasing subsequences aa modulo 109+7109+7.

Example

input

Copy
4
5
6 4 8 6 5
4
1 2 3 4
3
3 2 2
4
4 5 6 5

output Weighted Increasing Subsequences solution codeforces

Copy
4
12
0
6
Note

In the first test case the following increasing subsequences of aa have not zero weight:

  • The weight of [a1]=[6][a1]=[6] is 11.
  • The weight of [a2]=[4][a2]=[4] is 11.
  • The weight of [a2,a3]=[4,8][a2,a3]=[4,8] is 11.
  • The weight of [a2,a4]=[4,6][a2,a4]=[4,6] is 11.

The sum of weights of increasing subsequences is 44.In the second test case there are 77 increasing subsequences of aa with not zero weight: 33 with weight 1133 with weight 22 and 11 with weight 33. The sum of weights is 1212.

Leave a Comment

Your email address will not be published.