Problem: Ladybugs

Want to try solving this problem? You can submit your code online if you log in or register.

Ladybugs

Input File: ladyin.txt
Output File: ladyout.txt
Time Limit: 1 second

You really like ladybugs. This is fortunate, as dozens of ladybugs have recently taken up residence in your garden. Every day they emerge into the sunlight and climb your garden fence. The fence is a series of regularly spaced posts which gleam brightly in the sun. The ladybugs settle into their favourite resting spots atop these posts.

$\includegraphics[width=12cm]{ladybug}$

Winter is nigh and you wish to protect the ladybugs from the rain. You set out to construct a rain shelter using a single length of ribbon propped up with toothpicks. To protect all the ladybugs, the ribbon must be long enough to cover all their favourite resting spots. Ribbon is not cheap, so you wish to use the shortest length of ribbon you possibly can. A ribbon of length k will cover precisely k adjacent fence posts.

For example, on the fence in the diagram above there are two ladybugs sitting on fence post 3 and one ladybug on each of 2, 6, 7 and 9. The ribbon rain shelter must cover all the posts from 2 through to 9 inclusive, so the shortest possible length of ribbon that covers all the ladybugs is 8.

Your task is to write a program to calculate the minimum length of ribbon that will cover all the ladybugs.

Input

The first line of the input file will contain a single integer N, the number of ladybugs in your garden ( 1 <= N <= 1000000). Each of the following N lines specify the favourite resting spot (fence post) of one of the ladybugs. Fence posts are numbered 1, 2, 3, ... starting from one end of the fence and going all the way to the other. You are guaranteed that there are no more than 1000000000 fence posts in total.

Output

Your output file should consist of a single integer L, the shortest length of ribbon that will protect all the ladybugs.

Sample Input

Sample Output

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.