ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Осеннее первенство школьников 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Лыжная гонка

Ограничение времени: 1.5 секунды
Ограничение памяти: 64 МБ
На этот раз к вам за помощью обратились организаторы Зимних Олимпийских игр 2014 года, которые, как известно, пройдут в городе Екатеринозаводске. И хотя до Олимпийских игр ещё целых пять с половиной лет, первый спортивный объект уже сдан в эксплуатацию. Им стала трасса для проведения соревнований по лыжным гонкам.
Несмотря на то, что на трассе установлено только новое и надёжное оборудование, организаторы хотят разработать план действий в случае его сбоя. Что, например, делать, если из-за поломки секундомера на финише можно будет определить лишь порядок, в котором финишировали спортсмены? Дело осложняется правилами, по которым проводятся лыжные гонки с раздельным стартом. Участники стартуют по очереди, с интервалом в 30 секунд, поэтому участник, финишировавший первым, не обязательно будет первым в итоговой таблице результатов. Например, если спортсмен, стартовавший вторым, придёт к финишу на 25 секунд позже стартовавшего первым, то это значит, что он прошёл дистанцию на 5 секунд быстрее, а значит, должен располагаться в итоговой таблице выше.
Вам поручили написать программу, которая по порядку, в котором финишировали спортсмены, вычислит для каждого из них самое высокое и самое низкое место, на котором он может оказаться в итоговой таблице.

Исходные данные

В первой строке записано целое число n — количество участников гонки (1 ≤ n ≤ 2000). Участники нумеруются целыми числами от 1 до n в том порядке, в котором они стартовали. Во второй строке записана перестановка чисел от 1 до n — порядок, в котором лыжники пришли на финиш. Числа в строке разделены пробелом.

Результат

Выведите n строк, в i-й строке должны быть записаны через пробел два числа — самое высокое и самое низкое место, которое мог занять i-й участник.

Пример

исходные данныерезультат
6
3 5 1 4 2 6
3 6
4 6
1 4
2 5
1 3
1 6
Автор задачи: Евгений Курпилянский, Алексей Самсонов
Источник задачи: Осеннее первенство школьников 2008
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1645. Лыжная гонка