대체

정수 $N$개로 이루어진 수열 $P_1,P_2,\ldots,P_N$이 주어진다. 다음 연산을 정확히 $N-1$번 수행하여 원소가 하나만 남도록 만들 때, 비용 합의 최솟값을 구하여라.

1. 현재 수열에서 서로 이웃한 두 원소를 고른다. 두 원소의 값을 $x,y$라고 하자.
2. 두 원소를 $\min(x,y)$ 하나로 대체한다. 나머지 원소들의 상대적인 순서는 바뀌지 않는다.
3. 이 연산의 비용은 $\max(x,y)$이다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스에 대해 비용 합의 최솟값을 한 줄에 하나씩 입력 순서대로 출력한다.

• $1\leq T\leq50\ 000$.
• $2\leq N\leq100\ 000$.
• $-{10}^9\le$ ().