시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.3 초 256 MB92555363.855%

문제

경기도의 명소 경기과학고등학교에는 $N$명의 학생이 있습니다. 악당 브루는 경기과학고의 학생들을 분열시킨 후 경기과학고등학교를 지배할 계획을 세우고 있습니다.

교내에 중요 공지가 있어 학생들이 모두 일렬로 줄을 서 있습니다. 악당 브루는 교내에 서울과학고에서 파견한 스파이가 숨어 있다는 소문을 퍼뜨려 학생들을 분열시키고자 합니다. 소문을 들은 학생들은 다양한 의견을 가졌습니다. 일부 학생들은 소문을 믿었지만, 일부 학생들은 믿지 않았습니다.

맨 앞에 서 있는 학생을 $i$번 학생이라고 합시다. $i$번 학생의 소문에 대한 의견, 즉 성향을 정수 $A_i$로 나타낼 수 있습니다. $A_i >0$이면 스파이가 있다고 믿고, $A_i <0$이면 스파이가 없다고 믿습니다. 소문에 대해 무관심한 학생들의 $A_i =0$입니다.

소문을 들은 학생들은 무리를 짓게 됩니다. 초기에는 인원 수가 1인 $N$개의 무리가 존재하고, 학생들의 친밀도는 0입니다. 각 무리의 초기 성향은 유일한 학생의 성향으로 정의됩니다. 이후 앞뒤로 인접한 무리가 합쳐지는 과정이 $N-1$번 반복되어 마지막에는 모두가 하나의 무리로 합쳐집니다.

성향이 $x$인 무리와 $y$인 무리가 합쳐지면, 성향 $x+y$인 무리가 됩니다. 하지만 $x$와 $y$의 부호가 다르면, 즉 두 무리의 의견이 다르면 충돌이 일어납니다. 결국 학생들의 친밀도는 $|xy|$만큼 감소합니다. 두 무리의 의견이 같거나, 한쪽 무리가 소문에 무관심하면 친밀도는 변화하지 않습니다.

만약 악당 브루가 운이 좋아 무리들이 적절한 순서로 합쳐진다면, 친밀도를 어디까지 떨어뜨릴 수 있는지 구해 봅시다. 즉, 가능한 최소 친밀도를 구해 봅시다.

입력

첫 줄에는 학생의 수를 나타내는 정수 $N$이 주어집니다.

둘째 줄에는 $A_1$, $A_2$, $\cdots$, $A_N$이 공백을 사이에 두고 주어집니다.

출력

악당 브루가 얻을 수 있는 친밀도의 최솟값을 출력합니다.

제한

  • $1 \le N \le 80$
  • $-10^6 \le A_i \le 10^6$

서브태스크

번호배점제한
14

$A_i > 0$ ($1 \le i \le N$)

210

$N \ge 2$, $A_1 < 0$이며, $2 \le i \le N$인 정수 $i$에 대해 $A_i > -A_1$이다.

38

$1 \le N \le 3$

422

$1 \le N \le 8$

556

추가 제한 조건이 없습니다.

예제 입력 1

6
1 2 -3 4 -5 -6

예제 출력 1

-74

예제 입력 2

5
-3 5 9 7 8

예제 출력 2

-87

출처

High School > 서울과학고등학교 > 2022 SciCom Qualification Test D번

채점 및 기타 정보

  • 예제는 채점하지 않는다.