PEG Judge - WC15 #3 - Electroshock Therapy

Woburn Challenge 2015-16 Round 3 - Junior Division

Problem 2: Electroshock Therapy

Having found the battle predictions to be inconclusive, Batman has decided to employ another powerful weapon to guarantee his victory against Superman – electricity! After all, the man of steel should be a good conductor.

Although Batman is a genius-level physicist, it doesn't take a genius to know that a stupendous amount of energy is required to bring down a being who draws his power from the sun. Clearly, the quantity of energy to weaken Superman is too massive to be stored and carried around in the Batmobile. Through a stroke of brilliancy, he realized that he could simply tap into the city's power grid. So his plan is as follows: Batman will engineer his mech-suit to conduct electricity without doing any harm to himself, the wearer. When the time is right, Batman will plug the suit into any point in the power grid that he will have hooked up before the battle. Then, he will grip both hands onto Superman's body (closing the circuit) and direct an immense wave of electricity through the man of steel.

The challenge of this plan is all in the preparation: properly wiring up the city's power grid to the street on which the battle will take place. Batman already knows the location of the battle, and he knows that on that street, there are N (1 ≤ N ≤ 500) adjacent buildings numbered from 1 to N. The i-th building (for i = 1..N) has a total of H_i (1 ≤ H_i ≤ 500) floors. From inspecting a map of the city's power system, Batman noticed that he will need to wire up every building on the street to maximize his power output. To make his circuit as resilient as possible, he has decided to also wire up every floor on each building to the same floors of adjacent buildings (if they exist). This way, if the connection breaks in any one building, the circuit is still quite likely to be connected. Wires will run horizontally along the top of buildings, vertically across the sides of buildings, as well as horizontally across each floor of each building. However, the same floor across two adjacent buildings will share a vertical wire.

For example, if there are N = 4 buildings with heights H = {2, 1, 3, 2}, his circuit should look as follows:

     _
 _  |_|_
|_|_|_|_|
|_|_|_|_|

Each horizontal and vertical unit of wiring will require the same length of wire. For example, the above structure will require 24 units of wire. Batman may be a billionaire, but you don't stay rich by wasting money. Thus, he would like to use the minimum amount of wiring to create his weapon. Can you help him determine the length required?

Input Format

The first line will contain a single integer N.
The second line will contain N space-separated integers, the values of H₁ through H_N respectively.