Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Боксёры

(Время: 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.TXTOUTPUT.TXT
11
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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 A. Атрибутика
 B. Боксёры
 C. Вечерний пейзаж города К
 D. Генные модификации
 E. Деревянный забор
 F. E равно эм це квадрат?
 G. Ёлочные украшения
 H. Железнодорожные тарифы
 I. Загадали? Угадаем!
 J. Искусство алхимии
 K. Йодакойн
 L. Клумбы

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru



доставка контейнера цена