15673번 - 헤븐스 키친 2

문제

작년의 시즌 1에 이어, 올해에는 헤븐스 키친 시즌 2가 방송된다. 이전 시즌까지는 모든 사람이 참가하는 토너먼트 형식의 대전을 진행했지만, 첫 시즌의 방영 이후 치솟은 인기에 힘입어 너무 많은 요리사가 지원해버린 탓에 모든 인원이 참여하는 토너먼트는 힘들게 되었다.

따라서 이번 시즌에는 참가자 수를 조금 줄이기 위해, 첫 경기는 지원자 중 일부를 뽑아 두 팀으로 나누어 팀전을 진행하려고 한다. 첫 경기가 끝난 뒤에는 선별된 본선 멤버들이 토너먼트를 진행할 것이지만, 이 문제에서는 그다지 중요한 내용은 아니다.

첫 경기는 다수가 한꺼번에 참여하는 경기이므로, 요리 실력뿐 아니라 협업 능력, 수많은 사람들 속에서 눈에 띌 만한 퍼포먼스 등이 중요하게 평가된다. 이를 종합적으로 평가하여, 각 요리사에 대한 "스타성 지수" 를 정수 하나로 나타낼 수 있다. 만약 이 값이 음수라면 해당 요리사는 방송을 재미없게 만든다는 것을 의미하며, 양수일 경우엔 방송에서 활약할 수 있는 사람이라는 의미가 된다. 값의 절댓값이 커질 수록 영향력은 커지게 된다.

첫 경기의 팀을 결성하는 과정은 다음과 같다.

1. 프로그램에 지원한 요리사 N명을 일렬로 줄세운다.
2. 연속하여 서 있는 1명 이상의 요리사 그룹을 고른다. 이 요리사들은 팀 1이 된다.
3. 첫 그룹과 겹치지 않도록 연속하여 서 있는 1명 이상의 요리사 그룹을 하나 더 고른다. 이 요리사들은 팀 2가 된다. 팀 1과 팀 2의 인원수는 같지 않아도 된다.

두 팀은 줄 내에서 꼭 붙어있을 필요가 없으며, 어떤 팀에도 속하지 않은 요리사가 있어도 된다.

각 팀의 종합 퍼포먼스는 구간에 속한 요리사들의 스타성 지수의 합이 된다. 물론 두 팀의 퍼포먼스가 충분히 클 경우 방송의 재미가 어느 정도 보장되는 것이 맞지만, 만일 두 팀의 퍼포먼스가 모두 음수가 될 정도로 최악인 경우, 조금 다른 의미의 명경기가 펼쳐져 방송의 흥미도가 높아질 수도 있다. 이를 반영하여 방송의 흥미도는 두 팀의 종합 퍼포먼스의 곱이 된다.

프로그램에 참가하고자 하는 요리사 N명에 대한 스타성 지수 분석은 마무리되었고, 요리사들을 일렬로 줄세우는 작업, 즉 위의 1번 과정까지 마친 상황이다. 이 상태에서 위 과정의 2, 3번 작업을 적절히 마쳤을 경우, 가장 재미있는 방송의 흥미도는 얼마가 될까?

입력

첫 줄에 요리사의 수 N이 입력된다. (2 ≤ N ≤ 10⁵)

다음 줄에 각 요리사의 스타성 지수 P_i가 공백으로 구분되어 주어진다. (-100 ≤ P_i ≤ 100)

출력

방송의 가능한 최대 흥미도를 출력한다.

제한

힌트