Боксёры
(Время: 3 сек. Память: 16 Мб Сложность: 61%)
Планета Цапамия имеет закон, согласно которому житель любой планеты, имеющий спортивные заслуги, считается уроженцем Цапамии (несмотря на то, что живёт и тренируется он в родной галактике). Если такой спортсмен участвует в Межгалактических играх и попадает в список лучших, то его результат автоматически добавляется не к результату его галактики, а к результату галактики, в которой расположена Цапамия, а сам спортсмен получает в подарок флот торговых кораблей от Галактического Императора.
Перед началом Межгалактических соревнований по боксу выяснилось, что сборную команду Цапамии представляют n боксёров, причём с каждой планеты прибыл ровно один боксёр и взял себе в качестве номера номер своей планеты (целое число от 1 до n).
Какое-то (возможно, нулевое) количество боксёров уже заняло свои места в строю для торжественной церемонии приветствия императора, если сколько-то мест в строю свободно, то это значит, что остальные боксёры ещё находятся в пути.
Император любит порядок, но при этом считает себя большим оригиналом. Так что для приветствия императора боксёры должны выстроиться в таком порядке, чтобы длина наибольшей возрастающей подпоследовательности их номеров была строго равна n–1 (меньше - непорядок, больше – слишком стандартно).
Зная, на каких местах стоят боксёры с какими номерами, и на какие места боксёры ещё не доехали, определите, сколькими различными способами могут выстроиться боксёры для приветствия Императора.
Входные данные
Входной файл INPUT.TXT содержит ровно 10 тестовых примеров.
Первая строка каждого тестового примера содержит целое число n (1 ≤ n ≤ 105) – количество боксёров (и планет, с которых эти боксёры прибыли).
Вторая строка содержит n целых чисел p1, p2, ..., pn (0 ≤ pi ≤ n) – расположение боксёров в строю. 0 обозначает, что место вакантно (и ждёт прибывшего боксёра). Гарантируется, что все ненулевые элементы попарно отличаются друг от друга.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – количество различных способов, которыми боксёры могут выстроиться для приветствия Императора.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1
0
2
0 0
2
2 0
2
1 2
3
0 0 0
3
1 0 0
3
0 1 2
3
3 1 2
3
2 0 0
3
0 3 0 | 0
1
1
0
4
1
1
1
2
2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
