Knak and the 3D Printer

Interview

Time limit1sMemory limit1024 MB

Summary

Given N bar heights of width 1, find the total surface area of the histogram solid, counting the top, bottom, and side faces.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

One day, Knak received a 3D printer as a gift from an acquaintance. Knak had long been interested in 3D printers and was excited, but could not think of what to make with it. So Knak decided to print a histogram that caught his eye using the 3D printer.

A histogram is a shape in which $N$ bars of the same width $1$ are placed in a row with no gaps. Knak will print this as a 3D model made of $N$ rectangular boxes, each with width and depth $1$ and height $h_i$ .

With no money to spare, Knak wants to be extremely frugal. He will leave the inside of the model hollow and use exactly as much material as the surface area. Given the information of the histogram, find the surface area of the 3D model.

Input

The first line contains an integer $N$ , the number of bars in the histogram. ( $1 \le N \le 32\,768$ )

The second line contains the heights of the bars, $h_1, h_2, \cdots, h_N$ , separated by spaces. ( $1 \le h_i \le 32\,768$ )

Output

Print the surface area of the 3D histogram model.

Examples2

Example 1
Input
```
3
3 1 2
```
Expected output
```
26
```
Example 2
Input
```
3
1 2 3
```
Expected output
```
24
```