Jeff has a sequence a1,a2,…,aN of non-negative integers. He is assigned a task to process Q queries of the following format: each query is described by two integers L≤R and asks to calculate the...

Jeff has a sequence a1,a2,…,aN of non-negative integers. He is assigned a task to process Q queries of the following format: each query is described by two integers L≤R and asks to calculate the number of triples (i,j,k), such that Laiak

Test Case 1:

10 1

5 5 1 1 5 5 1 1 5 6

1 10

Result:

8