求助

题目

题目描述

小 A 遭受了怪物的攻击。这种怪物只有两种攻击方式：方式A和方式B。

小 A 有一个防护盾，可以：

• 防护方式A的攻击无限次。
• 防护方式B的攻击** $9$ 次**。
• 在防护方式B的攻击 $9$ 次后，这个护盾会破碎，无法防御新的攻击。

现在告诉你怪物攻击了 $n$ 次小A, 对于第 $i$ 次攻击：

• 如果 $A_i = 1$, 说明这是方式A的攻击。
• 如果 $A_i = 2$, 说明这是方式B的攻击。

请问小 A 最多可以防御多少次攻击？

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $A_i$。

或者，输入形如这样的格式：

n
A1 A2 A3 ... An

输出格式

一个整数，表示小 A 最多可以防御多少次攻击。

样例一

input

20
2 2 1 2 1 1 1 2 1 2 2 1 1 2 2 2 2 2 2 1

output

16

数据范围

对于 $100\%$ 的数据，保证 $1 \leq n \leq 1000$，$A_i$ 是 $1$, $2$ 中的一个。

---

时间限制：$1\texttt{s}$

空间限制：$1024\texttt{MB}$