Problemstellung

JOI-kun ist in der $1$. Klasse der Grundschule. JOI-kun liebt die Addition und Subtraktion, die er gerade erst gelernt hat, und wann immer er eine Reihe von Zahlen sieht, spielt er damit, eine Gleichung zu bilden, indem er zwischen die letzten $2$ Zahlen ein = setzt und zwischen die übrigen benachbarten Zahlen jeweils ein + oder - einfügt. Zum Beispiel kann er aus 8 3 2 4 8 7 2 4 0 8 8 die Gleichung 8+3-2-4+8-7-2-4-0+8=8 bilden.

Nachdem JOI-kun eine Gleichung gebildet hat, rechnet er nach, um zu überprüfen, ob es sich um eine richtige Gleichung handelt. Allerdings kennt JOI-kun noch keine negativen Zahlen und kann auch nicht mit Zahlen rechnen, die größer als $20$ sind. Daher sind unter den richtigen Gleichungen nur diejenigen für JOI-kun überprüfbar, bei denen beim Auswerten der linken Seite von links nach rechts alle im Verlauf der Rechnung auftretenden Zahlen mindestens $0$ und höchstens $20$ betragen. Beispielsweise ist 8+3-2-4-8-7+2+4+0+8=8 zwar eine richtige Gleichung, aber da das zwischendurch auftretende 8+3-2-4-8 eine negative Zahl ergibt, kann JOI-kun nicht überprüfen, ob diese Gleichung richtig ist.

Schreiben Sie ein Programm, das bei einer gegebenen Zahlenfolge als Eingabe die Anzahl der richtigen Gleichungen bestimmt, die JOI-kun bilden und überprüfen kann.

Eingabe

Die Eingabedatei besteht aus $2$ Zeilen. Die $1$. Zeile enthält eine ganze Zahl $N$ ($3 \le N \le 100$), die die Anzahl der aufgereihten Zahlen angibt. Die $2$. Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen, die mindestens $0$ und höchstens $9$ sind.

In $60\%$ der gegebenen Eingabedaten überschreitet die Anzahl der richtigen Gleichungen, die JOI-kun bilden und überprüfen kann, nicht $2^{31}-1$. Außerdem überschreitet in allen gegebenen Eingabedaten die Anzahl der richtigen Gleichungen, die JOI-kun bilden und überprüfen kann, nicht $2^{63}-1$.

Ausgabe

Geben Sie in $1$ Zeile eine ganze Zahl aus, die die Anzahl der richtigen Gleichungen angibt, die JOI-kun bilden und überprüfen kann.

Ein-/Ausgabebeispiele

Eingabebeispiel 1

11
8 3 2 4 8 7 2 4 0 8 8

Ausgabebeispiel 1

10

Eingabebeispiel 2

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

Ausgabebeispiel 2

7069052760

Im Eingabebeispiel $1$ kann JOI-kun die folgenden $10$ richtigen Gleichungen bilden und überprüfen:

• 8+3-2-4+8-7-2-4-0+8=8
• 8+3-2-4+8-7-2-4+0+8=8
• 8+3+2+4-8-7+2-4-0+8=8
• 8+3+2+4-8-7+2-4+0+8=8
• 8+3+2-4+8-7+2+4-0-8=8
• 8+3+2-4+8-7+2+4+0-8=8
• 8-3+2+4-8+7+2+4-0-8=8
• 8-3+2+4-8+7+2+4+0-8=8
• 8-3+2-4+8+7+2-4-0-8=8
• 8-3+2-4+8+7+2-4+0-8=8

Daher wird $10$ ausgegeben.

Beachten Sie im Eingabebeispiel $2$, dass die Antwort nicht in den Wertebereich einer vorzeichenbehafteten $32$-Bit-Ganzzahl passt.

(Nachtrag vom $21$. $2$. $2015$) Durch den Hinweis eines Nutzers wurde festgestellt, dass unter den Gleichungen in der Erklärung zu Eingabebeispiel $1$ ein Fehler vorlag. Dieser ist nun korrigiert. Die $5$. Gleichung lautete 8+3-2-4+8-7+2+4-0-8=8 und wurde zu 8+3+2-4+8-7+2+4-0-8=8 korrigiert. Außerdem lautete die $6$. Gleichung 8+3-2-4+8-7+2+4+0-8=8 und wurde zu 8+3+2-4+8-7+2+4+0-8=8 korrigiert.