Penguin Fall Response Committee
Time limit2sMemory limit512 MB
Given a line of N blocks with break costs and one marked penguin position, find the minimum total cost to break blocks so the penguin's group falls off the line.
- Level
Medium6 of 10
- Topics
- Greedy, Array, Prefix sum, Implementation
- Solved
- No attempts yet
Problem
Ilwoo is playing the penguin ice-breaking game with his friends. Feeling sorry for the penguin that keeps falling, Ilwoo invited the participants of the INU New Year Code Festival to the Penguin Fall Response Committee. This penguin ice-breaking game is a remake, with N ice blocks numbered from 1 to N. The game takes place on a line where the ice blocks are arranged in order from 1 to N. At the start, a single penguin stands on an arbitrary ice block K. The participants aim to make the penguin fall by breaking some of the ice blocks. However, the ice block the penguin is standing on cannot be broken. Each ice block has a different strength, so breaking ice block i (1 ≤ i ≤ N) requires A_i units of power. When adjacent ice blocks on both sides are viewed as one group, if the group's ends do not include ice block 1 or N, the group falls down. Consider the example below.
Ice block 4 and ice block 1 can be broken by applying 2 and 7 power, respectively. Now the group consisting of ice blocks 2 and 3, where the penguin stands, does not include ice block 1 or ice block 5, so it falls down. In the example above, the minimum power needed to make the penguin fall is 2+7=9.
As the Penguin Fall Response Committee, we want to find the minimum power with which a player can make the penguin fall and use it to prevent the falls. What is the minimum power that can make the penguin fall?
Input
The first line gives N (3 ≤ N ≤ 200,000), the number of ice blocks.
The next line gives the integers A_i (1 ≤ A_i ≤ 1,000,000,000) in order, where A_i is the power needed to break the i-th ice block.
As an exception, the position where the penguin stands is marked with -1, and there is no case where the penguin stands on ice block 1 or N.
Output
Print an integer representing the minimum power with which a player can make the penguin fall.