Se mantiene un multiconjunto de cajas, cada una con una cantidad de raciones; al principio está vacío. Llegan \(Q\) cambios: se agrega una caja con \(c\) raciones o se quita una caja que tiene exactamente \(c\) raciones.

Para vaciar todas las cajas, cada día se elige una de estas acciones:

1. elegir una caja no vacía y consumir todas sus raciones, o
2. consumir una ración de cada caja no vacía.

Después de cada cambio, calcula la mínima cantidad de días necesaria para vaciar todas las cajas (las raciones no se consumen de verdad: cada pregunta es independiente).

Entrada

La primera línea tiene un entero \(Q\) \((1 \le Q \le 3 \cdot 10^5)\).

La segunda línea tiene \(Q\) enteros con signo \(X_1, \dots, X_Q\) \((1 \le |X_i| \le 10^9)\) en orden cronológico: \(X_i = +c\) agrega una caja con \(c\) raciones y \(X_i = -c\) quita una caja con exactamente \(c\) raciones. Se garantiza que cada caja quitada existe.

Salida

Una línea con \(Q\) enteros: el \(i\)-ésimo es la mínima cantidad de días justo después del \(i\)-ésimo cambio.

Ejemplo 1

Entrada

8
+1 +2 +2 +7 -2 +10 -1 -2

Salida

1 2 2 3 3 4 3 2

Ejemplo 2

Entrada

2
+42 -42

Salida

1 0

Regional Latinoamericana 2025 del ICPC, problema E («Emergency Rations»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.