Busy Beaver adora pasar sus tardes en el Banana Lounge del MIT. ¡Decide ayudar apilando cajas de plátanos! Necesita recolectar el inventario de $N$ habitaciones consecutivas, dispuestas en una sola fila y numeradas del 1 al $N$ de izquierda a derecha. Debido a la peculiar arquitectura de los edificios del MIT, cada habitación $i$ tiene una altura de techo específica, $h_i$.
Busy Beaver necesita seleccionar una habitación $k$ ($1 \le k \le N$) para que sirva como Centro Principal (Main Hub). Luego, $N$ de sus amigos, uno de cada habitación, transportan cada uno una pila vertical de cajas de plátanos desde su habitación de origen $i$ directamente a la habitación central $k$. Dado que deben caminar en línea recta, la cantidad máxima de cajas que pueden transportar está limitada por la altura mínima en su camino.
Formalmente, la cantidad de cajas de plátanos entregadas por el amigo que comienza en la habitación $i$ a la habitación central $k$ es:
- $\min(h_i, h_{i+1}, \dots, h_k)$ si $i \le k$.
- $\min(h_k, h_{k+1}, \dots, h_i)$ si $i > k$.
La cantidad total de cajas de plátanos reunidas en el centro es la suma de las cajas entregadas por los $N$ amigos, que es:
$$\sum_{i=1}^{k-1} \min(h_i, \dots, h_k) + h_k + \sum_{i=k+1}^{N} \min(h_k, \dots, h_i)$$
Afortunadamente, Busy Beaver tiene un amigo en las Instalaciones del MIT. Antes de que los amigos comiencen a transportar las cajas, puede solicitar renovar como máximo una habitación (que no puede ser la habitación central elegida $k$) para cambiar su altura de techo $h_i$ a cualquier valor.
¿Cuál es la cantidad total máxima de cajas de plátanos que Busy Beaver puede reunir en el Centro Principal después de elegir la ubicación central óptima $k$ y realizar como máximo una renovación de techo?
Entrada
La primera línea contiene un solo entero $T$ ($1 \le T \le 10^5$) — el número de casos de prueba. La primera línea de cada caso de prueba contiene un solo entero $N$ ($2 \le N \le 10^6$). La siguiente línea de cada caso de prueba contiene $N$ enteros separados por espacios $h_1, h_2, \dots, h_N$ ($1 \le h_i \le 10^9$). La suma de $N$ en todos los casos de prueba no supera $10^6$.
Salida
Para cada caso de prueba, imprima una línea que contenga un entero: la respuesta para el caso de prueba.
Subtareas
Hay dos subtareas para este problema.
- (30 puntos): La suma de $N$ en todos los casos de prueba no supera $3 \cdot 10^3$.
- (70 puntos): Sin restricciones adicionales.
Ejemplos
Entrada 1
2 5 1 10 1 10 1 5 10 10 10 10 10
Salida 1
32 50
Nota
En el primer caso de prueba, la mejor opción es elegir el centro $k = 2$ y renovar $h_3$ a al menos 10, permitiendo que los tres amigos del medio transporten 10, para un total de 32.
En el segundo caso de prueba, ninguna renovación puede aumentar la cantidad de cajas de plátanos, por lo que la respuesta es 50.