이사

타로는 이사를 하게 되었다. 짐이 많아서 이삿짐센터에 운반을 맡기기로 했다. 짐의 무게가 제각각이라 알아보기 쉽도록 가벼운 것부터 순서대로 놓아 달라고 부탁했지만, 이삿짐센터 직원은 짐을 뒤죽박죽인 순서로 놓아 버렸다. 그래서 타로는 짐을 다시 정렬하려 했지만 짐이 무거워서 옮기는 데 체력이 든다. 각 짐은 지금 있는 자리에서 다른 짐 사이든 짐의 끝이든 원하는 곳으로 옮길 수 있지만, 어떤 짐을 옮기는 데에는 그 짐의 무게만큼 체력을 쓴다. 타로는 체력이 별로 없어서, 되도록 체력을 아끼면서 짐을 가벼운 것부터 순서대로 놓는 방법을 생각하기로 했다.

n
x1 x2 ... xn

• n은 타로가 가진 짐의 개수를 나타낸다
• x1부터 xn은 각 짐의 무게를 나타내며, 현재 x1, x2, …, xn의 순서로 놓여 있다

S

• 짐을 가벼운 것부터 순서대로 놓는 데 필요한 최소 체력의 합 S를 출력하라. 마지막에 개행을 출력해야 한다

• 1 ≤ n ≤ 105
• 1 ≤ xi ≤ n (1 ≤ i ≤ n)
• xi ≠ xj (1 ≤ i, j ≤ n이고 i ≠ j)
• 입력은 모두 정수로 주어진다