Asrit 有 $n$ 包馍片，它们排成一排。馍片共有 $5$ 种不同的味道：香葱味、孜然味、烧烤味、麻辣味、牛肉味。为了方便，我们将味道分别记为 $1 \sim 5$，其中第 $i$ 包馍片的味道为 $a_i$。

每当 Asrit 吃一包馍片时，他会获得 $1$ 点开心度。但是，总是吃同一种味道的馍片会很乏味。具体来说，如果 Asrit 先吃了一包味道为 $x$ 的馍片，紧接着吃的下一包馍片味道为 $y$，则他会额外获得 $(y - x + 5) \bmod 5$ 点开心度。

为了吃得更美味，Asrit 决定调整吃馍片的顺序。他会按照初始顺序依次处理每一包馍片，对于当前处理的馍片，选择是否将其扔到序列的最后。注意，一包馍片不能被扔两次，不然它会碎掉。

处理完所有馍片后，Asrit 会按照新的顺序依次吃掉它们。请问 Asrit 可以获得的最大开心度是多少？

Input

第一行输入一个整数 $n$ $(1 \le n \le 10^5)$，表示馍片的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 5)$，表示每包馍片的味道。

Output

输出一行一个整数，表示 Asrit 能获得的最大开心度。

Examples

Input 1

6
1 1 1 1 1 1

Output 1

6

Input 2

6
5 5 4 3 2 1

Output 2

26

Input 3

6
1 1 2 3 4 5

Output 3

15

Note

样例 $3$ 解释：将第 $1$ 包馍片和第 $6$ 包馍片扔到最后，最后吃的序列为 1 2 3 4 1 5，此时答案最大。