Background

Special for beginners, ^_^

Description

在一个给定的序列中，寻找一个最长的子序列（不要求连续），使得该子序列的和是3的倍数。

Format

Input

本题包含多组测试例。

第一行n，表示共有n$(\le10^6)$个数。

第二行共n个自然数，用一个空格隔开，每个数不超过$10^{19}$。

单个测试点的n求和不超过$10^7$。

Output

对于每个测试例，在一行中输出一个整数，表示所求子序列的最大长度。

Samples

6 
1 2 2 1 2 5

5

Limitation

1s, 1024KiB for each test case.