HAPPINESS - Happiness

You are given an array on N elements a[1], a[2], a[3], ... a[N].

Now you will have to answer some queries.

In every query, you will be given an interval, [l, r]. For this interval you have to print the total summation of happiness of all the elements of the given array between the interval [l, r].

The happiness of an element a[i] between interval [l, r] is: the number of sub-array [lj, rj] where the minimum value between [lj, rj] is equal to a[i]. Here, l <= lj <= i and i <= rj <= r.

Now, you have to print the total summation of happiness of all the elements between [l, r].

Input

The first line of the input contains the number of test cases T. The first line of each test case contains two numbers, N and M. N is the number of elements in array a and M is the number of queries you need to perform.

The next line contains N integers, the array a: a[1], a[2], a[3], ... a[N].

Next M lines contains two integers, l and r.

Constraints

1 <= T <= 5

1 <= N, M <= 50000

1 <= a[i] <= 1000000000

1 <= l <= r <= N

Output

For each test case, you need to print the case number on the first line in this format: Case X: where X is the case number.

In the next M lines, you need to print the total summation of happiness of all the elements between [l, r] of the given array.

Example

Input:
2
5 2
1 3 2 4 3
1 3
2 4
5 2
5 3 7 6 8
1 4
2 5 Output: Case 1:
6
6
Case 2:
10
10

Problem Setter: Raihat Zaman Neloy. Used in Eid 2016 contest. For more about Eid 2016 contest: Click Here


Added by:Raihat Zaman Neloy
Date:2016-07-22
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2016-08-07 17:36:06 kataria
WTF
2016-07-29 08:41:09
I think so that all elements are not distinct

Last edit: 2016-07-29 08:41:40
2016-07-26 16:25:28 Mitch Schwartz
@problem setter: Note that the challenge section is for problems with special scoring.

Last edit: 2016-07-26 17:53:19
2016-07-22 15:42:18 Francky
What is the challenge ?
Maybe the best place is classical section.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.