시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB116433437.363%

문제

피에스고등학교의 교장 이환이는 학교를 매우 사랑한다. 그래서 이환이는 매일 점심시간에 학교의 모든 건물을 돌아다닌다. 비가 오는 어느 날, 이환이는 학교 곳곳을 돌아다니고 싶었지만 비를 끔찍이 싫어하기 때문에 그럴 수 없었다.

비 때문에 고민하던 이환이는 결국 비를 맞지 않고 학교의 모든 건물을 방문할 수 있도록 건물과 건물 사이에 구름다리를 설치하기로 했다. 하지만 학생들은 비가 오는 날마저 이환이가 돌아다니면 게임을 하다 걸릴까 봐 구름다리 설치를 반대했다. 건물 $i$와 다른 건물을 잇는 구름다리가 $k$개 설치되면, 건물 $i$에서 게임을 하던 학생들은 $k$개의 구름다리에서 이환이가 오는지 확인해야 하기 때문에 $k^2$ 만큼의 불만을 가진다.

점심시간에 건물 1에는 학생 1명, 건물 2에는 학생 2명, 건물 3에는 학생 3명이 게임한다고 가정하자. 아래와 같이 구름다리를 건설하면 건물 2와 건물 3에 있는 학생들은 불만을 1씩 가지고 건물 1에 있는 학생은 불만을 4 가진다. 따라서 이때 생기는 학생들의 불만은 $1 \times 4 + 2 \times 1 + 3\times 1 = 9$이다. 불만이 9보다 작도록 구름다리를 건설하는 것은 불가능하다.

실제로 피에스고등학교에는 $N$개의 건물이 있고, $i$번 건물에서는 $a_i$명의 학생이 게임을 한다. 학생의 불만이 크면 이환이가 상처받기 때문에, 이환이를 위해 불만의 최솟값을 구해줘야 한다.

입력

첫 번째 줄에 건물의 수 $N$이 주어진다.

두 번째 줄에는 각 건물에서 게임을 하는 학생의 수를 나타내는 음이 아닌 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 불만의 최솟값을 출력한다.

제한

  • $1 \leq N \leq 3 \times 10^5$
  • $0 \leq a_i \leq 10^6$ $(1 \le i \le N)$
  • 입력으로 주어지는 수는 모두 정수이다.

예제 입력 1

3
1 2 3

예제 출력 1

9

출처