33830번 - Turniej trójek 다국어

W Bajtowie odbył się właśnie wielki turniej w grę Bajt: Bitmingham. W jednej rozgrywce w Bajt: Bitmingham bierze udział dokładnie trzech graczy, którzy muszą spotkać się w jednym miejscu, żeby móc przeprowadzić rozgrywkę.

Jak prawdopodobnie dobrze wiesz, w Bajtowie jest tylko jedna, długa droga, przy której stoi $n$ budynków, ponumerowanych kolejno liczbami od $1$ do $n$.

Dla wygody graczy ustalono, że jeśli trójka graczy mieszka w budynkach o numerach $a$, $b$ i $c$ to rozgrywka zostaje przeprowadzone w środkowym z tych budynków, czyli budynku o numerze będącym medianą z liczb $a$, $b$ i $c$. W szczególności, jeśli dwóch graczy mieszka w tym samym budynku $x$, to niezależnie od miejsca zamieszkania trzeciego gracza, rozgrywka odbędzie się w budynku $x$.

Przygotowujesz podsumowanie statystyk turnieju. Wiesz, że każda trójka graczy zagrała ze sobą co najwyżej raz. Dla każdego budynku wiesz, ile rozgrywek zostało w nim przeprowadzonych: dla budynku numer $i$ było to $a_i$ rozgrywek. Jednak zapomniałeś się dowiedzieć, ilu było graczy w turnieju. . .

Oblicz, jaka jest minimalna możliwa liczba graczy biorących udział w turnieju, która nie jest sprzeczna z informacjami jakie posiadasz.

Musisz rozwiązać ten problem dla $t$ niezależnych przypadków testowych.

W pierwszym wierszu wejścia znajduje się liczba $t$ ($1 ≤ t ≤ 50$), oznaczająca liczbę przypadków testowych.

Każdy przypadek testowy jest opisany przez dwa wiersze. W pierwszym z tych wierszy znajduje się liczba całkowita $n$ ($1 ≤ n ≤ 200\, 000$), oznaczająca liczbę budynków w Bajtowie. W drugim wierszu znajduje się ciąg liczb całkowitych $a_1, a_2, \dots , a_n$ ($0 ≤ a_i ≤ 1\, 000\, 000$), oznaczający, ile rozgrywek odbyło się w kolejnych budynkach. Możesz założyć, że co najmniej jedna wartość $a_i$ jest dodatnia.

Suma wartości $n$ po wszystkich przypadkach testowych nie przekroczy $200\, 000$.

Na wyjściu powinno znaleźć się $t$ wierszy, w $i$-tym z nich powinna znaleźć się jedna liczba całkowita, oznaczająca minimalną liczbę osób, jaka mogła brać udział w turnieju.

Wyjaśnienie przykładu: W pierwszym przypadku testowym do przeprowadzenia jednej rozgrywki potrzeba $3$ graczy. W drugim przypadku testowym jest $57$ rozgrywek; $8$ graczy nie wystarczy, gdyż byłoby wtedy tylko $\binom{8}{ 3} = 56$ różnych trójek, potrzebny jest więc dziewiąty gracz. W trzecim przypadku testowym w każdym budynku mógł mieszkać jeden gracz:

• w drugim budynku odbyły się rozgrywki pomiędzy graczami z budynków $1$, $2$, $3$; $1$, $2$, $4$ oraz $1$, $2$, $5$;
• w trzecim budynku odbyły się rozgrywki pomiędzy graczami z budynków $1$, $3$, $4$; $1$, $3$, $5$; $2$, $3$, $4$ oraz $2$, $3$, $5$;
• w czwartym budynku odbyły się rozgrywki pomiędzy graczami z budynków $1$, $4$, $5$; $2$, $4$, $5$ oraz $3$, $4$, $5$.

W czwartym przypadku testowym nie wystarczy $5$ graczy, bo w któryś budynku byłoby ich co najwyżej dwóch, a to za mało, żeby znaleźć $4$ trójki o odpowiedniej medianie