ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2015

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

K. Садовод Кирилл 3

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Садоводу Кириллу дали новое задание — полить цветы, растущие на огромной клумбе! Надо заметить, что клумба очень длинная, но очень узкая, поэтому с высоты птичьего полёта (и даже роста Кирилла) она похожа на прямую, на которой на одинаковом расстоянии находятся n точек-цветов. Для выполнения задания Кирилл располагает лейкой бесконечного объёма и умными часами, которые перед началом полива для каждого цветка указали его увлажнённость. Так как полив занимает длительное время, наименее увлажнённые цветы могут успеть засохнуть, чего никак нельзя допустить! Поэтому Кирилл решил поливать цветы в порядке неубывания их увлажнённости. С другой стороны, закончить полив ему хочется как можно скорее, ведь есть ещё столько интересных дел.
Будем считать, что и полив одного цветка, и переход между двумя соседними цветами Кирилл осуществляет за одну минуту. Сможете посчитать время, за которое справится юный садовод, если будет действовать оптимально? Изначально Кирилл стоит около самого левого цветка клумбы.

Исходные данные

В первой строке дано целое число n (1 ≤ n ≤ 105) — количество цветов на клумбе. Во второй строке дано n целых чисел через пробел — увлажнённости цветов в порядке их расположения на клумбе слева направо. Все увлажнённости — целые числа от 1 до 109 включительно.

Результат

В единственной строке выведите целое число — минимальное время, за которое Кирилл сможет закончить полив.

Пример

исходные данныерезультат
6
3 2 5 6 2 5
21

Замечания

Один из способов успеть за 21 минуту на тестовом примере:
  1. Идём от 1-го до 5-го цветка (4 минуты)
  2. Поливаем 5-й цветок (1 минута)
  3. Идём от 5-го до 2-го цветка (3 минуты)
  4. Поливаем 2-й цветок (1 минута)
  5. Идём от 2-го до 1-го цветка (1 минута)
  6. Поливаем 1-й цветок (1 минута)
  7. Идём от 1-го до 3-го цветка (2 минуты)
  8. Поливаем 3-й цветок (1 минута)
  9. Идём от 3-го до 6-го цветка (3 минуты)
  10. Поливаем 6-й цветок (1 минута)
  11. Идём от 6-го до 4-го цветка (2 минуты)
  12. Поливаем 4-й цветок (1 минута)
Автор задачи: Илья Кучумов
Источник задачи: Уральская региональная командная олимпиада по программированию 2015
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2072. Садовод Кирилл 3