思路

• 关键观察：

  • 设元素按模 $3$ 的余数为 $0,1,2$。相邻两项之和能被 $3$ 整除，当且仅当余数对为 $(0,0),(1,2),(2,1)$。
  • 若子序列包含余数为 $0$ 的元素，则相邻也只能是 $0$。因此包含 $0$ 余数的三好子序列只能全部由余数为 $0$ 的元素组成。
  • 含有余数为 $1,2$ 的三好子序列必须在 $1$ 与 $2$ 之间交替。

• 因此最大和来源只有两类：

题目内容

给定一个由 $n$ 个整数构成的数组 {$a_1,a_2,…,a_n$} 。

如果一个子序列的长度为 $1$ 、或其任意相邻两项之和均为 $3$ 的倍数，则称其为 三好子序列 。

请你从原数组中选出一个三好子序列，使其元素之和最大，输出该最大和。

【名词解释】 子序列：指从原序列中删除若干元素后，保持相对顺序得到的新序列。

输入描述

第一行输入一个整数 $n(1 ≦n ≦2×10^5)$ ，表示数组的长度。 第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≦a_i≦ 10^6)$ ，表示数组元素。

输出描述

输出一个整数，表示最大三好子序列的元素和。

样例1

输入

6
1 1 4 5 1 4

输出

13

说明

在数组 {$1,1,4,5,1,4$} 中，所有满足任意相邻两项之和为 $3$ 的倍数的子序列中，和最大的三好子序列为 {$4,5,4$} ，它对应原序列下标 {$3,4,6$} ，其元素和为 $4+5+4=13$ 。