A - Optimization of Circular Security Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ある街の中央広場に、円形に N 個の街灯が等間隔に設置されています。街灯には時計回りに 1, 2, \ldots, N と番号が付けられており、街灯 N の次は街灯 1 に繋がっています。

最初、すべての街灯にちょうど 1 人ずつ、合計 N 人の警備員が配置されています。街灯 i の警備員を撤収させるのにかかる費用は A_i です。

高橋君は予算削減のため、何人かの警備員を撤収させたいと考えています。ただし、防犯上の理由から少なくとも 2 人の警備員を残さなければならず、さらに、すべての操作が完了した後に残っている警備員は全員、次の安心条件を満たさなければなりません：

  • 安心条件：街灯 i に警備員が残っている場合、街灯 i から時計回りにちょうど \lfloor N/2 \rfloor 個先の街灯と、反時計回りにちょうど \lfloor N/2 \rfloor 個先の街灯のうち、少なくとも一方にも警備員が残っていなければならない。

ここで、街灯 i から時計回りに k 個先の街灯とは、街灯 ((i - 1 + k) \bmod N) + 1 のことです。反時計回りに k 個先の街灯とは、街灯 ((i - 1 - k + N) \bmod N) + 1 のことです。なお、\bmod は非負の剰余を表します。

N が偶数の場合、時計回りに \lfloor N/2 \rfloor 個先と反時計回りに \lfloor N/2 \rfloor 個先は同じ街灯（街灯 i のちょうど対角の街灯）を指します。このとき安心条件は、その対角の街灯に警備員が残っていることと同値になります。

警備員の撤収には次のルールが適用されます：

  • 高橋君は0回以上、好きな回数だけ操作を行えます。
  • 各操作では、円形上で時計回りに連続する 1 個以上 N 個以下の街灯からなる区間を 1 つ選びます。街灯 N と街灯 1 をまたぐ区間も選べます。選んだ区間に含まれる街灯のうち、まだ警備員が残っている街灯すべてから警備員を撤収させます。既に警備員が撤収済みの街灯が区間に含まれていても構いません（その街灯では何も起きません）。
  • 各操作のコストは、その操作で実際に撤収させた警備員の撤収費用の最大値です。実際に撤収させた警備員が 1 人もいない場合、その操作のコストは 0 です。

高橋君の目標は、すべての操作が完了した後に、

  1. 残った警備員が 2 人以上であり、
  2. 残った警備員全員が安心条件を満たしている

ことです。この条件を満たすような操作の手順すべての中で、操作のコストの合計の最小値を求めてください。

操作を一度も行わなくても上記の条件がすべて満たされている場合、コストの合計は 0 です。

制約

  • 2 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数である。

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、街灯の数を表す整数 N が与えられる。
  • 2 行目には、各街灯の警備員の撤収費用を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

操作のコストの合計の最小値を 1 行で出力せよ。

入力例 1

5
3 1 4 1 5

出力例 1

0

入力例 2

4
8 2 6 10

出力例 2

0

入力例 3

11
12 7 25 3 18 30 5 14 9 21 16

出力例 3

0

入力例 4

20
100 35 82 47 91 23 64 58 76 12 89 41 67 29 95 53 18 70 44 61

出力例 4

0

入力例 5

2
1000000000 1

出力例 5

0

Score : 200 pts

Problem Statement

In the central square of a town, N lampposts are installed at equal intervals in a circle. The lampposts are numbered 1, 2, \ldots, N in a clockwise order, and lamppost N is connected to lamppost 1.

Initially, exactly one guard is stationed at each lamppost, making a total of N guards. The cost to withdraw the guard at lamppost i is A_i.

Takahashi wants to withdraw some guards to cut costs. However, for security reasons, at least 2 guards must remain, and furthermore, all remaining guards after all operations must satisfy the following safety condition:

  • Safety Condition: If a guard remains at lamppost i, there must be a guard remaining at at least one of the following: the lamppost exactly \lfloor N/2 \rfloor positions clockwise from lamppost i, or the lamppost exactly \lfloor N/2 \rfloor positions counterclockwise from lamppost i.

Here, the lamppost k positions clockwise from lamppost i refers to lamppost ((i - 1 + k) \bmod N) + 1. The lamppost k positions counterclockwise from lamppost i refers to lamppost ((i - 1 - k + N) \bmod N) + 1. Note that \bmod represents the non-negative remainder.

If N is even, the lamppost \lfloor N/2 \rfloor positions clockwise and the lamppost \lfloor N/2 \rfloor positions counterclockwise refer to the same lamppost (the lamppost directly opposite to lamppost i). In this case, the safety condition is equivalent to requiring that a guard remains at that opposite lamppost.

The following rules apply to withdrawing guards:

  • Takahashi can perform operations any number of times (possibly zero).
  • In each operation, he chooses an interval of 1 to N consecutive lampposts clockwise along the circle. The interval can wrap around from lamppost N to lamppost 1. He withdraws the guards from all lampposts in the chosen interval that still have guards. It is fine if some lampposts in the interval already have their guards withdrawn (nothing happens at those lampposts).
  • The cost of each operation is the maximum withdrawal cost among the guards actually withdrawn in that operation. If no guards are actually withdrawn, the cost of the operation is 0.

Takahashi's goal is to ensure that after all operations are completed:

  1. At least 2 guards remain, and
  2. All remaining guards satisfy the safety condition.

Find the minimum total cost of operations among all valid sequences of operations that achieve this goal.

If all the conditions are already satisfied without performing any operations, the total cost is 0.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of lampposts.
  • The second line contains N space-separated integers A_1, A_2, \ldots, A_N, representing the withdrawal costs of the guards at each lamppost.

Output

Print the minimum total cost of operations in a single line.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

0

Sample Input 2

4
8 2 6 10

Sample Output 2

0

Sample Input 3

11
12 7 25 3 18 30 5 14 9 21 16

Sample Output 3

0

Sample Input 4

20
100 35 82 47 91 23 64 58 76 12 89 41 67 29 95 53 18 70 44 61

Sample Output 4

0

Sample Input 5

2
1000000000 1

Sample Output 5

0