20367번 - 3 Slot Matching

무수히 넓은 우주에서는 한 국가의 영역을 결정하기 위해, 특이한 땅따먹기 게임을 한다고 전해진다. 이 게임은 N개의 막대쌍과 3개의 슬롯을 가지고 진행된다. 막대쌍은 위아래로 차례로 쌓여있으며, 맨 위의 막대쌍을 제외한 다른 막대기는 건드릴 수 없다.

참가자는 아래 2가지 중 하나를 선택하여 행동하는 것을 원하는 만큼 반복할 수 있다.

• 맨 위에 있는 막대쌍 하나를 가져와 비어있는 슬롯에 보관한다.
• 슬롯에 보관되어 있는 막대쌍 두 개를 꺼내어, 각 막대기를 변으로 하는 직사각형을 만들고 그 직사각형으로 둘러쌓인 공간을 영역으로 인정받는다.

그렇게 만들어진 모든 직사각형 영역의 넓이의 합이 그 국가의 면적이 된다. 맨 위에 있는 막대쌍을 슬롯에 넣지 않고 버리거나, 슬롯에 있는 막대쌍을 임의로 버릴 수 없다. 모든 행동은 주어진 선택지 두 가지 중 하나여야 한다.

이번에는 희권국의 영역을 결정할 차례이다. 희권이가 N개의 막대쌍의 순서와 길이를 전부 알고 있다고 할 때, 희권국이 인정받을 수 있는 영역의 총면적의 최댓값은 얼마일까?

첫째 줄이 N (2 ≤ N ≤ 3000)이 주어진다.

둘째 줄에 위에서부터 i번째에 있는 막대쌍의 길이를 나타내는 정수 A_i (1 ≤ A_i ≤ 10⁶)가 공백으로 구분되어 주어진다.

희권국이 인정받을 수 있는 영역의 총면적의 최댓값을 나타내는 정수를 출력하시오.