402817: GYM100889 A A Beautiful Array

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. A Beautiful Arraytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Little Tinu is a handsome kid and likes only beautiful things. He has an array and wants its most beautiful permutation. The beauty of a 1-indexed array A is defined as:

where is integer division.Input

The first line contains T(1 ≤ T ≤ 10), the number of test cases. Every test case contains 2 lines. First line has an integer N(1 ≤ N ≤ 103), the size of the array A. Second line contains the array A as space separated integers(0 ≤ Ai ≤ 106).

Output

Output for each test case, the maximum beauty of any permutation of the array A.

ExampleInput
2
3
3 2 1
4
1 40 70 40
Output
2
69
Note

Sample test case 1:

There are 6 permutations possible:

Beauty  = 2

Beauty  = 1

Beauty  = 1

Beauty  =  - 1

Beauty  =  - 1

Beauty  =  - 2

Maximum of all beauties is 2.

Sample test case 2:

The best permutation is [1, 40, 70, 40] where beauty is 69.

加入题单

上一题 下一题 算法标签: