주먹밥 합치기

알퐁스는 여러 가지 크기의 주먹밥 N개를 한 줄로 놓아 두었다. 친구에게 줄 주먹밥을 가능한 한 크게 만들려고 한다. 알퐁스는 다음 두 연산을 쓸 수 있다.

• 크기가 같은 주먹밥 두 개가 서로 인접해 있으면, 그 두 개를 합쳐 새 주먹밥 하나를 만들 수 있다. 새 주먹밥의 크기는 두 주먹밥의 크기를 더한 값이고, 원래 두 주먹밥이 있던 자리를 차지한다.
• 크기가 같은 주먹밥 두 개 사이에 주먹밥이 정확히 하나 있으면, 그 세 개를 한꺼번에 합쳐 새 주먹밥 하나를 만들 수 있다. 가운데 주먹밥의 크기는 양쪽과 같지 않아도 된다. 새 주먹밥의 크기는 세 주먹밥의 크기를 더한 값이고, 원래 세 주먹밥이 있던 자리를 차지한다.

두 연산은 각각 원하는 만큼 여러 번 쓸 수 있다.

연산을 0번 이상 수행한 뒤 줄에 남은 주먹밥 중 가장 큰 것의 크기를 구하라.

첫째 줄에 정수 N이 주어진다. ($1 \le N \le 400$)

둘째 줄에 주먹밥의 크기를 왼쪽부터 차례대로 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 정수는 1 이상 1,000,000 이하이다.

알퐁스가 만들 수 있는 가장 큰 주먹밥의 크기를 출력한다.