Конфеты на празднике


Отправить решение Решать в редакторе

Сложность: 48%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Конфеты на празднике

В очереди стоят n детей, у i-го оценка rᵢ за поделку. Каждому нужно дать хотя бы одну конфету, а ребёнок с оценкой строго выше, чем у соседа (слева или справа), должен получить конфет строго больше этого соседа. Какое наименьшее общее число конфет понадобится?

Формат ввода

В первой строке n (1 ≤ n ≤ 10⁵). Во второй — n чисел rᵢ (1 ≤ rᵢ ≤ 10⁹).

Формат вывода

Наименьшее число конфет.

Пример 1

Вход:

3
1 3 2

Выход:

4

Комментарии

Еще нет ни одного комментария.