2322번 - 아령

한 헬스장에 n개의 무게가 서로 다른 아령들이 있다.

헬스장을 사용하는 사람들의 편의를 위해, 아령은 무게가 작은 것부터 무거운 것까지 헬스장에 걸려 있다. 하지만 매일 사람들이 이 아령을 사용한 뒤에 아무 위치에나 걸어놓기 때문에, 하루가 끝나고 나면 아령의 순서들은 뒤섞이기도 한다.

당신은 이제 이 아령들을 원래 순서대로 걸어 놓으려고 한다. 이를 위해서는 이미 걸려있는 아령을 들고, 다른 손으로 다른 아령을 하나 들고, 두 아령의 위치를 바꾸는 작업을 해야 한다. 그리고 이와 같은 작업을 여러 번 반복해야 한다. 아령들이 너무 무겁기 때문에 이와 같은 작업을 한 번 마친 뒤에는 반드시 잠시 휴식을 취해야 한다고 가정하자. 즉, 두 아령의 위치를 바꾸는 작업만을 할 수 있는 것이다. 이와 같은 작업을 할 때 각 아령의 무게만큼의 힘이 든다고 하자.

당신은 가급적이면 적은 힘을 들여서 아령을 원래 순서대로 걸어 놓으려고 한다. 아령이 걸려 있는 순서가 주어졌을 때, 필요한 최소의 힘을 구하는 프로그램을 작성하시오.

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 걸려 있는 순서대로 아령의 무게가 주어진다. 각 아령의 무게는 2³⁰보다 작거나 같은 자연수이며 답이 2³¹-1보다 작거나 같게 되도록 주어진다.

첫째 줄에 필요한 최소의 힘을 출력한다.