Cigle

다른 현실인 Earth 616에서 어린 스테판은 전혀 다른 삶을 산다. 그는 예술디자인학교의 벽돌 공예 과정에 등록되어 있다. 그곳의 다른 아이들처럼 그도 패턴에 빠져 있다. 예를 들어 그의 숙제는 $N$개의 벽돌로 벽을 쌓는 것이다. 하지만 그는 이차원 스케치가 마음에 들 때까지 쌓기를 시작하지 않는다.

스케치에서 모든 벽돌은 높이가 1이고 너비가 $d_i$인 직사각형으로 그린다. 그는 벽돌의 순서를 미리 정하고, 가장 아래 줄부터 스케치를 시작한다.

첫 번째 줄에서는 왼쪽에서 오른쪽으로 벽돌을 몇 개든 놓는다. 두 번째 줄에서는 오른쪽에서 왼쪽으로 벽돌을 놓되, 두 번째 줄의 첫 벽돌은 첫 줄의 마지막 벽돌과 오른쪽 끝이 맞춰진다. 다음으로 세 번째 줄에서는 다시 왼쪽에서 오른쪽으로 놓는다. 세 번째 줄의 첫 벽돌은 두 번째 줄의 마지막 벽돌과 이번에는 왼쪽 끝이 맞춰진다. 벽돌이 남지 않을 때까지 이 과정을 반복한다. 벽의 줄 수는 원하는 만큼 정할 수 있다.

스테판은 초강력 시멘트를 쓰므로, 벽돌 바로 아래에 다른 벽돌이 없도록 벽돌을 놓을 수 있다. 벽의 아름다움은 벽돌 4개가 맞닿는 곳의 개수이다.

주어진 벽돌의 순서와 각 크기에 대해, 만들 수 있는 벽의 아름다움의 최댓값을 구하라.

첫 줄에 문제에서 주어지는 정수 $N$이 주어진다.

둘째 줄에 문제에서 주어지는 $N$개의 정수 $d_i$가 주어진다.

만들 수 있는 벽 중 아름다움의 최댓값을 출력한다.

$M$을 가장 넓은 벽돌의 너비라 하자. 별도로 언급하지 않는 한 $1 \le M \le 5000$이 성립한다.

세 번째 예시에서 아름다움이 4인 벽은 다음과 같다.