Выгодная покупка (30 баллов)
Автор задачи: Рогачева Е.В.
Задачу добавил: alef
Успешно сдано решений: 54
У NN выдался свободный день, который он решил посвятить путешествию по K лучшим книжным магазинам города MM (K >= 3). Ему хотелось приобрести книгу, которая была издана недавно и еще не "добралась" до его родного города. Принцип путешествия таков: переходя из магазина в магазин NN помнит только последние две цены (обозначим их С1 и С2). В очередном магазине он видит "текущую" цену (обозначим ее C3). Если текущая цена оказалась выше предыдущей, он расстраивается, а если C1 < C2 < C3, он расстраивается настолько, что прекращает свое путешествие. Если это не так, он надеется найти в дальнейшем лучшую цену и продолжает путешествие. Книгу он купит в последнем магазине, если доберется до него, и указанное выше условие не будет выполнено.
Надо выяснить, сколько существует маршрутов, заканчивающихся успехом (приобретением книги).
Формат входного файла input.txt
Первая строка - целое число K (3<=K<=20) - количество магазинов.
Вторая строка содержит K вещественных чисел с точностью 2 знака после запятой - цены на искомую книгу в магазинах.
Формат выходного файла output.txt
Целое число - число успешных маршрутов
Пример входного файла
Пример выходного файла