問題ヴィジュアル

問題文

チェリーちゃんはクロワッサンを持っている. 各クロワッサンの味は $1$ 以上 $N$ 以下の整数で表され, 味 $i$ のクロワッサンは $A_i$ 個持っている.

チェリーちゃんは「持っているクロワッサンから $1$ 個を選び. そのクロワッサンを食べる」という行動を $0$ 回以上繰り返して, 多くのクロワッサンを食べたい.

ただし, チェリーちゃんは飽き性なので, 以下のルールを守らなければならない.

• $2$ 個目以降に食べるクロワッサンは, その直前に食べたクロワッサンとは味が異なっていなければならない.

チェリーちゃんは最大で何個のクロワッサンを食べることができるか?

$T$ 個のテストケースについて答えよ.

制約

• $1 \leq T \leq 10^5$.
• 各テストケースに対する制約
  • $1 \leq N \leq 3 \times 10^5$.
  • $1 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$.
• テストファイルに対する制約.
  • $T$ 個のテストケースにおける $N$ の総和は $3 \times 10^5$ 以下である.

入力

$T$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_T$

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

出力は $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には, 第 $t$ テストケースに関する解答を出力せよ.

サンプル

3
3
1 2 3
1
46
6
15 18 42 87 15 93

6
1
270