eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кубики

Кубики

Лимит времени 1 секунда
Лимит использования памяти 32 MiB

Незважаючи на те, що Петрик П’яточкін ходить до школи, він все ще продовжує гратися з кубиками. З однакових кубиків він викладає сходинки вздовж стіни. Для цього складає стовпчики з кубиків таким чином:

  • перший стовпчик стоїть впритул до стіни;

  • другий стовпчик стоїть впритул до стіни і впритул до першого стовпчика праворуч від нього;

  • третій стовпчик стоїть впритул до стіни і впритул до другого стовпчика праворуч від нього і так далі...

Висоти стовпчиків не зростають при розгляданні сходинок зліва направо. Інакше кажучи, якщо h_i — висота i‑го стовпчика, то h_1h_2h_3 ≥ ... .

Петрик встановлює кубики у деякій послідовності. Він встановив для себе такі правила:

  1. кубик, розташований не на підлозі, можна поставити лише після кубика, на якому він має стояти. Інакше кажучи, не можна підсовувати кубики під вже поставлені;

  2. кубик, який знаходиться не у першому стовпчику, можна поставити лише після встановлення кубика, розташованого ліворуч від нього.

Знайти кількість різних способів послідовного встановлення кубиків, у результаті яких виникнуть сходи з заданими висотами стовпчиків h_1, h_2, ..., h_k. Враховують лише ті способи, що задовольняють умови (1) та (2).

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

Перший рядок вхідного файлу містить натуральне число k — кількість стовпчиків (1k6).

Другий рядок вхідного файлу містить k натуральних чисел h_1, h_2, ..., h_k — кількості кубиків відповідно у першому, другому, … , k‑му стовпчику сходів (6h_1h_2 ≥ ... ≥ h_k1).

Єдиний рядок вихідного файлу має містити кількість різних способів розташування кубиків у задану конфігурацію згідно з вказаними правилами (1) і (2) при даних висотах стовпчиків.

Для цього прикладу вкажемо допустимі послідовності розташування кубиків. Номер кожного кубика вказує, яким за рахунком його ставлять.

Пример

Входные данные #1
3
2 2 1
Выходные данные #1
5