Boxes And Balls

Ivan에게는 서로 다른 상자 n개가 있다. 그중 첫 번째 상자에는 서로 다른 색 n가지의 공이 들어 있다.

Ivan은 이상한 게임을 하려고 한다. 그는 모든 i (1 ≤ i ≤ n)에 대해 i-th 상자에 색 i인 모든 공이 들어 있도록 공을 상자에 분배하려고 한다.

이를 위해 Ivan은 몇 번의 턴을 진행한다. 각 턴에 그는 다음을 수행한다:

1. Ivan은 비어 있지 않은 임의의 상자를 하나 선택하고 이 상자에서 모든 공을 꺼낸다;
2. Then Ivan은 임의의 빈 상자 k개를 선택하고(첫 번째 단계의 상자는 비게 되므로 Ivan은 그 상자를 선택해도 된다), 이전 단계에서 꺼낸 공을 비어 있지 않은 그룹 k개로 나누어 각 그룹을 상자 중 하나에 넣는다. 각 그룹은 서로 다른 상자에 넣어야 한다. 그는 k = 2 또는 k = 3 중 하나를 선택할 수 있다.

한 턴의 페널티는 Ivan이 그 턴의 첫 번째 단계에서 상자에서 꺼낸 공의 수이다. 그리고 게임의 페널티는 Ivan이 모든 공을 해당하는 상자에 분배할 때까지 진행한 턴들의 페널티 합이다.

게임에서 가능한 최소 페널티를 구하도록 Help Ivan!

첫 번째 줄에는 하나의 정수 n (1 ≤ n ≤ 200000) — 상자와 색의 수가 주어진다.

두 번째 줄에는 정수 n개 a1, a2, ..., an (1 ≤ ai ≤ 109)가 주어지며, 여기서 ai는 색 i인 공의 수이다.

하나의 수 — 게임에서 가능한 최소 페널티를 출력한다.

첫 번째 예제에서는 첫 번째 상자에서 모든 공을 꺼내고, k = 3을 선택한 뒤 모든 색을 해당하는 상자로 분류한다. 페널티는 6이다.

두 번째 예제에서는 두 번의 턴을 진행한다:

1. 첫 번째 상자에서 모든 공을 꺼내고, k = 3을 선택한 뒤 색 3인 공은 세 번째 상자에, 색 4인 공은 네 번째 상자에 넣고 나머지는 첫 번째 상자에 다시 넣는다. 페널티는 14이다;
2. 첫 번째 상자에서 모든 공을 꺼내고, k = 2를 선택한 뒤 색 1인 공은 첫 번째 상자에, 색 2인 공은 두 번째 상자에 넣는다. 페널티는 5이다.

총 페널티는 19이다.