Asrit에게는 일렬로 놓인 만터우 칩 $n$봉지가 있다. 칩에는 파 맛, 쿠민 맛, 바비큐 맛, 마라 맛, 소고기 맛의 $5$가지 서로 다른 맛이 있다. 편의를 위해 각 맛을 $1 \sim 5$로 표시하며, $i$번째 봉지의 맛은 $a_i$이다.

Asrit는 칩 한 봉지를 먹을 때마다 행복도 $1$을 얻는다. 하지만 항상 같은 맛의 칩을 먹는 것은 지루하다. 구체적으로, Asrit가 맛이 $x$인 칩 한 봉지를 먹은 직후 맛이 $y$인 칩 한 봉지를 먹으면, 행복도 $(y - x + 5) \bmod 5$를 추가로 얻는다.

더 맛있게 먹기 위해 Asrit는 칩을 먹는 순서를 바꾸기로 했다. 그는 초기 순서대로 각 봉지를 처리하며, 현재 처리하는 봉지를 수열의 맨 뒤로 던질지 선택한다. 한 봉지를 두 번 던지면 부서지므로 두 번 던질 수 없다는 점에 주의하라.

모든 봉지를 처리한 후 Asrit는 새로운 순서대로 칩을 먹는다. Asrit가 얻을 수 있는 행복도의 최댓값은 얼마인가?

입력

첫 번째 줄에는 칩 봉지의 수를 나타내는 정수 $n$ $(1 \le n \le 10^5)$이 주어진다.

두 번째 줄에는 각 봉지의 맛을 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 5)$가 주어진다.

출력

Asrit가 얻을 수 있는 행복도의 최댓값을 나타내는 정수 하나를 한 줄에 출력하라.

예제

입력 1

6
1 1 1 1 1 1

출력 1

6

입력 2

6
5 5 4 3 2 1

출력 2

26

입력 3

6
1 1 2 3 4 5

출력 3

15

참고

예제 $3$의 설명: $1$번째 봉지와 $6$번째 봉지를 맨 뒤로 던지면, 최종적으로 먹는 순서는 $1,2,3,4,1,5$가 되고 이때 답이 최대이다.