헤븐스 키친 2

작년 시즌 1에 이어 올해는 헤븐스 키친 시즌 2가 방송된다. 지난 시즌까지는 지원자 전원이 겨루는 토너먼트로 진행했지만, 시즌 1이 방영된 뒤 인기가 치솟아 지원한 요리사가 너무 많아졌다. 이제 전원이 참가하는 토너먼트는 열기 어렵다.

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

첫 경기는 여러 명이 한꺼번에 참여하는 경기라, 요리 실력뿐 아니라 협업 능력, 수많은 사람 속에서 눈에 띌 만한 퍼포먼스도 중요하게 평가한다. 이를 종합해 요리사마다 스타성 지수를 정수 하나로 나타낼 수 있다. 이 값이 음수라면 그 요리사는 방송을 재미없게 만든다는 뜻이고, 양수라면 방송에서 활약할 수 있는 사람이라는 뜻이다. 절댓값이 커질수록 영향력도 커진다.

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

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

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

각 팀의 종합 퍼포먼스는 그 팀에 속한 요리사의 스타성 지수 합이다. 두 팀의 퍼포먼스가 충분히 크면 방송의 재미가 어느 정도 보장되지만, 두 팀의 퍼포먼스가 모두 음수일 만큼 최악이라면 조금 다른 의미의 명경기가 펼쳐져 방송의 흥미도가 높아지기도 한다. 이를 반영해 방송의 흥미도는 두 팀의 종합 퍼포먼스를 곱한 값으로 정한다.

요리사 $N$명의 스타성 지수 분석은 마무리되었고, 요리사를 일렬로 줄세우는 1번 과정까지 마친 상황이다. 이 상태에서 2번과 3번 과정을 적절히 마쳤을 때, 가장 재미있는 방송의 흥미도는 얼마인가?

첫 줄에 요리사의 수 $N$이 주어진다. ($2 \le N \le 10^5$)

다음 줄에 각 요리사의 스타성 지수 $P_1, P_2, \dots, P_N$이 공백으로 구분되어 주어진다. ($-100 \le P_i \le 100$)

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