Migrated from Lutece 293 Minimum Sum

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You are given $N$ positive integers, denoted as $x_0, x_1\cdots x_{N-1}$. Then give you some intervals $[l, r]$. For each interval, you need to find a number $x$ to make $\sum_{i=l}^{r}|x-x_i|$ as small as possible!

Input

The first line is an integer $T$ ($T\leq 10$), indicating the number of test cases. For each test case, an integer $N$ ($1\leq N\leq 100,000$) comes first. Then comes $N$ positive integers $x$ ($1\leq x\leq 1,000, 000,000$) in the next line. Finally, comes an integer $Q$ ($1\leq Q\leq 100,000$), indicting there are $Q$ queries. Each query consists of two integers $l$, $r$ ($0\leq l\leq r < N$), meaning the interval you should deal with.

Output

For the $k_{th}$ test case, first output Case #k: in a separate line. Then output $Q$ lines, each line is the minimum value of $\sum_{i=l}^{r}|x-x_i|$. Output a blank line after every test case.

Samples

2

5
3 6 2 2 4
2
1 4
0 2

2
7 7
2
0 1
1 1

Case #1:
6
4

Case #2:
0
0

Resources

2010 ACM-ICPC Multi-University Training Contest 13 Host by UESTC