3.选数（xshu）

题目描述

小红喜欢 1，小紫喜欢 2，小彩喜欢 3。 现在他们拿到了一个仅由 1、2、3 组成的长为 $n$ 的数组 $a$，她们可以进行若干次如下操作：

• 小红可以选择数组中的任意一个 1，将其变为 0 并获得 1 分，之后将与其相邻的两个元素变为 0。
• 小紫可以选择数组中的任意一个 2，将其变为 0 并获得 2 分，之后将与其相邻的两个元素变为 0。
• 小彩可以选择数组中的任意一个 3，将其变为 0 并获得 3 分，之后将与其相邻的两个元素变为 0。

现在小彩想知道，她们最多可以获得多少分？

输入格式

第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$）。 第二行输入 $n$ 个整数 $a_i$（$1 \le a_i \le 3$）。

输出格式

输出一个整数，代表她们所能获得的最高分数。

样例 1

输入

5
1 2 1 3 1

输出

5

说明

她们会选择数组中的 2 和 3。