특별한 물리 공격

NLCS Jeju에는 화재 경보가 울리면 모든 커플이 헤어진다는 징크스가 있다...

시이(swi)는 해야 할 공부는 하지 않고 연애만 하는 학생들이 NLCS Jeju에 너무 많다고 보고, 이들에게 시이-빔을 쏘아 단죄하기로 했다.

언제나처럼 화재경보기가 오작동해 학생 $N$명이 대피하여 운동장에 한 줄로 서 있다. 시이는 커플인 두 사람 중 한 명 이상을 단죄하려고 한다. 하지만 누가 커플인지 알 수 없으므로, 시이는 다음 규칙에 따라 학생들을 단죄하기로 했다.

• 서로 인접한 두 학생 중 한 명 이상을 반드시 단죄해야 한다.

각 학생은 시이-빔에 대한 저항력이 있다. 앞에서 $i$번째 학생을 시이-빔으로 단죄하려면 $R_i$만큼의 에너지가 필요하다.

이러한 시이의 행동에 분노한 학생들은 몇 명의 머리를 대머리로 만들어 시이-빔을 반사하려 한다. 대머리인 학생에게 시이-빔을 쏘면 빔이 대머리에 반사되어 시이가 공격을 입게 된다. 따라서 시이는 대머리가 아닌 학생에게만 시이-빔을 쏠 수 있다. 다만 이웃한 두 학생을 모두 대머리로 만들 수는 없다. 그렇게 하면 단죄당하느니만 못하게 되기 때문이다.

학생들은 일부 인원의 머리를 적절히 밀어, 시이가 단죄에 성공하는 데 필요한 최소 에너지를 최대화하려 한다. 학생들이 대머리를 정했을 때 그 최소 에너지가 최대가 되는 경우에, 시이가 소모해야 하는 총 에너지를 구하라.

첫 번째 줄에 학생의 수를 나타내는 정수 $N$이 주어진다.

두 번째 줄에 각 학생의 저항력을 나타내는 정수 $R_i$가 공백을 사이에 두고 주어진다.

학생들이 대머리를 정해 시이가 소모해야 하는 최소 에너지가 최대가 되었을 때, 시이가 소모해야 하는 총 에너지를 정수로 출력한다.

• $1 \le N \le 100\,000$
• $1 \le R_i \le 10^9$
• 학생들이 머리를 밀기 전에 대머리인 학생은 존재하지 않는다.