github.com/captn3m0/codechef.git

---
languages_supported:
    - NA
title: L4
category: NA
old_version: true
problem_code: L4
tags:
    - NA
layout: problem
---
###  All submissions for this problem are available. 

Two friends live in a small city. The city is built in the form of a circular road and skyscrapers surrounding the road. But one day the two friends quarreled with each other, and although they remained in the city, they decided to live in apartments located as far as possible from each other, or more precisely, so as to maximize the travel time between them. All the skyscrapers are arranged in a circle around the road (so you can travel in a cycle as follows: 1 <-> 2 <-> 3 <-> ... <-> n <-> 1), and the travel time between two neighbouring buildings is 1. The travel time between two adjacent floors of a skyscraper is also 1, and the friends can choose to live in any floor of the building, from the 0-th to the k-th, assuming that the skyscraper in question has k floors. Thus, the travel time from the j-th floor to ground level is j time units.

### Input

First, 1 <= n <= 106, the number of skyscrapers. The following numbers, 1 <= h1 <=109,...1 <= hn <= 109, are the heights of the buildings, given in clockwise order.

### Output

Output exactly one number, the maximal possible travel time.

### Example

<pre><b>Input:</b>
4 1 2 3 4

<b>Output:</b>
8
<b>Input:</b>
10 1 7 4 3 2 9 2 3 4 5

<b>Output:</b>
20

</pre>**Please note: the time limit for this problem is _extremely_ strict!**