На этот раз к вам за помощью обратились организаторы Зимних Олимпийских игр 2014 года, которые, как известно, пройдут в городе Екатеринозаводске. И хотя до Олимпийских игр ещё целых пять с половиной лет, первый спортивный объект уже сдан в эксплуатацию. Им стала трасса для проведения соревнований по лыжным гонкам.

Несмотря на то, что на трассе установлено только новое и надёжное оборудование, организаторы хотят разработать план действий в случае его сбоя. Что, например, делать, если из-за поломки секундомера на финише можно будет определить лишь порядок, в котором финишировали спортсмены? Дело осложняется правилами, по которым проводятся лыжные гонки с раздельным стартом. Участники стартуют по очереди, с интервалом в 30 секунд, поэтому участник, финишировавший первым, не обязательно будет первым в итоговой таблице результатов. Например, если спортсмен, стартовавший вторым, придёт к финишу на 25 секунд позже стартовавшего первым, то это значит, что он прошёл дистанцию на 5 секунд быстрее, а значит, должен располагаться в итоговой таблице выше.

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

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

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