shunfurh
编程介的小学生
2017-12-03 06:01

How Many W

  • as
  • c
  • each

Problem Description
Given a sequence (S_1, S_2, ..., S_N) (1 <= S_i <= 1,000,000,000, S_i != S_j), count the number of W, which can be regarded as a quintuple (a, b, c, d, e) satisfying a < b < c < d < e, S_b < S_c < S_a, S_d < S_c < S_e.

Input
The beginning of the input is an integer T, which is the number of test cases. T cases are followed. The first line of each test case is an integer N (1 <= N <= 100,000), which denotes the length of the sequence. The second line is N integer S_1, S_2, ..., S_N, which denote the sequence.

Output
For each test case, print a line contains a single integer which is the number of W, modulo 1,000,000,007.

Sample Input
2
5
5 1 3 2 4
6
6 1 3 4 2 5

Sample Output
1
3

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答

为你推荐

换一换