L. Идеальная фотография
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп является тренером команды по волейболу. Сейчас в его команде $$$n$$$ игроков, причем рост $$$i$$$-го игрока равен $$$a_i$$$. Гарантируется, что в команде нет двух и более игроков с одинаковым ростом.

Поликарп хочет сделать идеальную фотографию игроков своей команды. Фотография считается идеальной, если выполняются следующие условия:

  • все игроки команды выстроены в ряд;
  • рост самого левого игрока может быть любым;
  • рост каждого игрока, кроме самого левого, должен быть ровно на $$$1$$$ больше, чем рост его соседа слева.

Поликарп может принять в команду любое количество игроков с любым ростом. Перед вами стоит задача определить минимальное количество новых игроков, которых нужно принять в команду, чтобы Поликарп смог сделать идеальную фотографию своей команды.

Входные данные

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество игроков в команде Поликарпа.

Во второй строке следует последовательность различных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно росту $$$i$$$-го игрока.

Выходные данные

Выведите минимальное количество новых игроков, которых нужно принять в команду, чтобы Поликарп смог сделать идеальную фотографию своей команды.

Примеры
Входные данные
4
200 195 197 199
Выходные данные
2
Входные данные
3
180 182 181
Выходные данные
0
Примечание

В первом примере нужно принять в команду двух игроков, одного с ростом $$$196$$$, а другого с ростом $$$198$$$.

Во втором примере не нужно никого принимать в команду, так как Поликарп может сделать идеальную фотографию изначального состава игроков.