Компʼютерна гра «RaiN» відбувається у двовимірному світі, який складається із блоків 1 на 1 (метр). Острови гравців – це набори стовпців різної висоти із блоків (каміння). Під час сильних дощів всі низини островів заповнюються водою. По ландшафту островів, визначте обʼєм води, який накопичується на кожному острові.

Формат вхідних даних

Вхідні дані – стандартне введення.

• в першому рядку записано натуральне число ~N~ ~(0 ≤ N ≤ 15)~ – кількість стовпців, які задають ландшафт острова.

• в другому рядку ~N~ натуральних чисел ~H_i~ ~(0 ≤ H_i ≤ 10^9)~ – висоти стовпців одного острова.

Формат вихідних даних

У стандартний потік виведіть одне число – обʼєм води накопичений на даному острові (кількість блоків зайнятих водою).

Приклад вхідних даних

11
2 5 2 3 6 9 3 1 3 4 6

Приклад вихідних даних

18

Пояснення

Приклад відповідає рисунку нижче. Чорним кольором позначене каміння, сірим – вода.