Copiado al portapapeles
Descripción
Se tiene n dulces colocados de izquierda a derecha sobre una mesa. Los dulces estan numerados de izquierda a derecha. El dulce i-esimo tiene un peso wi. Pedro y Juan comen dulces.
Pedro puede comer cualquier cantidad de dulces de la izquierda (no puede saltarse los dulces, los come en fila)
Juan puede comer cualquier cantidad de dulces de la derecha (no puede saltarse los dulces, los come en fila)
Por supuesto, si Pedro comio un dulce, Juan no puede comerselo, y viceversa
Quieren ser justos. Su objetivo es comer el mismo peso total de dulces. Puedes averiguar cual es la cantidad maxima de dulces que pueden comer en total
Entrada
La primera linea contiene un entero t (1 <= t <= 104) el numero de casos de prueba.
La primera linea de cada caso de prueba contiene un numero entero n (1 <= n <= 2 * 105) la cantidad maxima de dulces en la mesa
La segunda linea de cada caso de prueba contiene n enteros w1, w2, ... , w3 (1 <= wi <= 104) que son los pesos de los dulces de izquierda a derecha.
Salida
Para cada caso de prueba imprima un solo numero entero: la cantidad maxima de dulces que Pedro y Juan pueden comer en total mientras cumplen la condicion dada.
Ejemplo Entrada
4 3 10 20 10 6 2 1 4 2 4 1 5 1 2 4 8 16 9 7 3 20 5 15 1 11 8 10
Ejemplo Salida
2 6 0 7