Busy Beaver는 MIT의 Banana Lounge에서 오후 시간을 보내는 것을 좋아합니다. 그는 바나나 상자를 쌓는 일을 돕기로 했습니다! 그는 왼쪽에서 오른쪽으로 1부터 $N$까지 번호가 매겨진 일렬로 배치된 $N$개의 연속된 방에 있는 재고를 수집해야 합니다. MIT 건물의 독특한 구조로 인해 각 방 $i$에는 특정 천장 높이 제한 $h_i$가 있습니다.

Busy Beaver는 메인 허브로 사용할 방 $k$ ($1 \le k \le N$) 하나를 선택해야 합니다. 그런 다음, 각 방에서 한 명씩, 총 $N$명의 친구가 각자의 시작 방 $i$에서 허브 방 $k$로 바나나 상자를 수직으로 쌓아 운반합니다. 그들은 직선으로 걸어가야 하므로, 운반할 수 있는 최대 상자 수는 경로상의 최소 높이 제한에 의해 제한됩니다.

공식적으로, 방 $i$에서 시작하여 허브 방 $k$로 배달되는 바나나 상자의 수는 다음과 같습니다:

• $i \le k$인 경우 $\min(h_i, h_{i+1}, \dots, h_k)$
• $i > k$인 경우 $\min(h_k, h_{k+1}, \dots, h_i)$

허브에 모인 바나나 상자의 총 개수는 모든 $N$명의 친구가 운반한 상자의 합이며, 다음과 같습니다:

$$\sum_{i=1}^{k-1} \min(h_i, \dots, h_k) + h_k + \sum_{i=k+1}^{N} \min(h_k, \dots, h_i)$$

다행히 Busy Beaver에게는 MIT 시설 관리팀에 친구가 있습니다. 친구들이 상자를 운반하기 전에, 그는 최대 하나의 방(선택된 허브 방 $k$는 제외)을 개조하여 해당 방의 높이 제한 $h_i$를 임의의 값으로 변경하도록 요청할 수 있습니다.

최적의 허브 위치 $k$를 선택하고 최대 한 번의 천장 개조를 수행한 후 Busy Beaver가 모을 수 있는 바나나 상자의 최대 총 개수는 얼마입니까?

입력

첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 10^5$)가 주어집니다. 각 테스트 케이스의 첫 번째 줄에는 정수 $N$ ($2 \le N \le 10^6$)이 주어집니다. 각 테스트 케이스의 다음 줄에는 $N$개의 공백으로 구분된 정수 $h_1, h_2, \dots, h_N$ ($1 \le h_i \le 10^9$)이 주어집니다. 모든 테스트 케이스에 대한 $N$의 합은 $10^6$을 넘지 않습니다.

출력

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다: 해당 테스트 케이스의 정답.

서브태스크

이 문제에는 두 개의 서브태스크가 있습니다.

• (30점): 모든 테스트 케이스에 대한 $N$의 합은 $3 \cdot 10^3$을 넘지 않습니다.
• (70점): 추가 제한 없음.

예제

입력 1

2
5
1 10 1 10 1
5
10 10 10 10 10

출력 1

32
50

참고

첫 번째 예제 케이스에서 가장 좋은 방법은 허브 $k = 2$를 선택하고 $h_3$를 10 이상으로 개조하여 중간의 세 친구가 모두 10개를 운반할 수 있게 하는 것이며, 총합은 32가 됩니다. 두 번째 예제 케이스에서는 어떤 개조를 하더라도 바나나 상자의 개수를 늘릴 수 없으므로 정답은 50입니다.