Description

Given a sequence $A=\{a_1,a_2,\ldots,a_n\}$, compute the sequence $B=\{b_1,b_2,\ldots,b_n\}$ from $A$, where:

$$b_i= \begin{cases} a_1 &, i=1 \\ \min_{1 \leq j < i}\left|a_i-a_j\right| &, i\gt 1 \end{cases}$$

Find $\sum\limits^n_{i=1}b_i$.

Input Format

The first line contains a positive integer $T$, the number of testdata sets. Then there are $T$ lines, each describing one set of testdata. Each line starts with a positive integer $n$, the number of elements in sequence $A$; then follow $n$ non-negative integers, which are $a_1,a_2,\ldots,a_n$ in order.

Output Format

For each testdata set, output the sum of all elements of sequence $B$.

2
5 1 2 3 4 5
7 2 9 7 4 6 2 6

5
14

Hint

Constraints: $1\le t\le 10$, $1\le n\le10^5$, $0\le a_i\le65536$.

Translated by ChatGPT 5