24940번 - Split the GSHS 서브태스크

문제

경기도의 명소 경기과학고등학교에는 $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$

서브태스크

힌트