题目描述

塔子哥很喜欢数圆。对于 $0$ 到 $9$ 来说，$0,6,9$ 各有一个圆，$8$ 有两个圆，其他数没有圆。比如数 $89$ 有三个圆，$998244353$ 有四个圆。

塔子哥有一个长度为 $n$ 的数组 $a$ ，塔子哥可以选择（也可以不选）一个区间 $[l,r]$ 使得 $a[l],a[l+1],\cdots,a[r]$ 都加 $1$ 。

现在塔子哥问你，在至多选择一个区间使得这个区间内所有的数都 $+1$ 的情况下，数组中所有数的圆的数量最大可以达到多少。

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$ 表示数组长度

第二行，$n$ 个整数表示数组 $a$ ，第 $i$ 个元素为 $a_i(0 \leq a_i \leq 10^9)$

输出描述

一个整数，表示在至多选择一个区间操作的情况下，数组中所有数的圆的数量可以达到的最大值。

样例

输入

10
1 3 5 7 9 2 4 6 8 10

输出

8

说明

将区间$[3, 4]$对应的数字每个加一后，数组变成 [1 3 6 8 9 2 4 6 8 10]

共有 8 个圆