Prefixos i sufixos P96912

Considereu un vector @v@ de $n$ nombres naturals. Trobeu el prefix més curt (però no buit) del vector tal que existeixi un sufix del vector amb la mateixa suma.

Per exemple, si @v@ és @[1, 2, 5, 6, 8, 9, 12, 4, 3]@, el prefix demanat és @[1, 2]@, el qual suma el mateix que el sufix @[3]@. Com un altre exemple, si @v@ és [3, 2, 3, 5, 2, 6, 1, 1, 1, 3, 1, 2, 4], el prefix és @[3, 2, 3, 5]@, amb la mateixa suma que @[1, 1, 1, 3, 1, 2, 4]@. Com a últim exemple, per a @[1, 2, 3, 4]@ el prefix és el vector sencer @[1, 2, 3, 4]@.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$, seguida dels $n$ naturals de @v@, tots entre 0 i $10^4$. Suposeu $1 \le n \le 10^5$.

Sortida

Per a cada cas, escriviu la longitud del prefix més curt que compleix la propietat demanada. Fixeu-vos que sempre existeix alguna solució.

Pista

La solució esperada té cost linial.