Problem description

Dawid jest kolekcjonerem krasnali ogrodowych. W jego kolekcji znajduje się N egzemplarzy, każdy o innej wysokości. Dawid chciałby ozdobić ogród swoimi krasnalami, ustawiając je wszystkie w jednym rzędzie w taki sposób, żeby wysokości sąsiednich krasnali różniły się o 1. Niestety, takie ustawienie może nie być możliwe (na przykład kiedy kolekcja składa się jedynie z dwóch krasnali o wysokościach 2 i 4). Pominięcie któregoś z posiadanych krasnali nie wchodzi w grę, ale Dawid jest skłonny dokupić kilka dowolnie wysokich sztuk, żeby zrealizować swój cel. Pomóż mu!

Napisz program, który wczyta opis kolekcji Dawida i wypisze minimalną liczbę krasnali, o które należy ją powiększyć, żeby ozdobienie ogrodu było możliwe.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba N, oznaczająca liczbę krasnali w kolekcji Dawida. W drugim wierszu znajduje się N parami różnych liczb całkowitych H_i pooddzielanych pojedynczymi odstępami, oznaczających wysokości kolejnych krasnali.

Wyjście

W pierwszym (jedynym) wierszu wyjścia wypisz minimalną liczbę krasnali, które Dawid musi dodać do swojej kolekcji, żeby mógł nią ozdobić ogród w wyżej opisany sposób.

Ograniczenia

2 ≤ N ≤ 1 000 000, 1 ≤ H_i ≤ 10¹⁸.

Przykład

3
8 3 5

3

2
1 2

0