Cho dãy N số nguyên a[1], a[2], …, a[N] được xếp thành một vòng tròn (tức là sau số a[N] là số a[1]). Hãy sắp xếp dãy này sao cho sau khi sắp xếp ta có tổng |a[1] – a[2]| + |a[2] – a[3]| + … + |a[N - 1] – a[N]| +|a[N] – a[1]| có giá trị lớn nhất.

Dữ liệu vào: 

• Dòng đầu tiên chứa một số nguyên T - số lượng test case. Trong đó, mỗi bộ dữ liệu gồm:

• Dòng đầu chứa số nguyên N
• Dòng thứ hai chứa N số nguyên được phân cách bằng dấu cách biểu thị các phần tử của dãy a[1], a[2], …, a[N]ed4ed4

Dữ liệu ra: 

• Với mỗi bộ dữ liệu đầu vào, in ra một dòng chứa tổng lớn nhất tìm được theo yêu cầu

Ràng buộc

• 1 ≤ T ≤ 100; 1 ≤ N ≤ 10⁴; 1 ≤ a[i] ≤ 10⁶, i = 1..N

Ví dụ: