Weighted Increasing Subsequences solution codeforces

You are given the sequence of integers $a_{1}, a_{2}, \dots, a_{n}$ of length $n$ .

The sequence of indices $i_{1} < i_{2} < \dots < i_{k}$ of length $k$ denotes the subsequence $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}}$ of length $k$ of sequence $a$ .

The subsequence $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}}$ of length $k$ of sequence $a$ is called increasing subsequence if $a_{i_{j}} < a_{i_{j + 1}}$ for each $1 \leq j < k$ .

The weight of the increasing subsequence $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}}$ of length $k$ of sequence $a$ is the number of $1 \leq j \leq k$ , such that exists index $i_{k} < x \leq n$ and $a_{x} > a_{i_{j}}$ .

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

Find the sum of weights of all increasing subsequences of $a$ modulo $10^{9} + 7$ .

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 1000$ ) — the number of test cases.

The first line of each test case contains the single integer $n$ ( $1 \leq n \leq 2 \cdot 10^{5}$ ) — the length of the sequence $a$ .

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ) — the sequence $a$ .

It is guaranteed that the sum of $n$ over all test cases doesn’t exceed $2 \cdot 10^{5}$ .

Output Weighted Increasing Subsequences solution codeforces

For each test case, print the sum of weights of all increasing subsequences $a$ modulo $10^{9} + 7$ .

Example

input

Copy

output Weighted Increasing Subsequences solution codeforces

Copy

Note

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

The weight of $[a_{1}] = [6]$ is $1$ .
The weight of $[a_{2}] = [4]$ is $1$ .
The weight of $[a_{2}, a_{3}] = [4, 8]$ is $1$ .
The weight of $[a_{2}, a_{4}] = [4, 6]$ is $1$ .

The sum of weights of increasing subsequences is $4$ .In the second test case there are $7$ increasing subsequences of $a$ with not zero weight: $3$ with weight $1$ , $3$ with weight $2$ and $1$ with weight $3$ . The sum of weights is $12$ .

For Solution

Click Here!

Weighted Increasing Subsequences solution codeforces

Weighted Increasing Subsequences solution codeforces

For Solution

Click Here!

Leave a Comment Cancel Reply

escorts dubai escorts dubai escorts dubai escorts dubai escorts dubai escorts dubai escorts dubai escorts dubai escort istanbul escort istanbul escort istanbul escort istanbul escort istanbul