Информатика

Как известно, при разработке и отладке программ большую помощь могут оказать игрушечные жёлтые уточки (см. статью «Метод утёнка» в википедии), поэтому Денис собрал большую коллекцию жёлтых уточек. Коллекция уже настолько большая, что Денис решил расставить уточек на полки шкафа. Сначала он начал ставить на каждую полку по A уточек, но одна уточка оказалась лишней. Тогда он заново начал расставлять уточек на полки, ставя на каждую полку по B уточек, но в этом случае ему не хватило одной уточки, чтобы на каждой полке оказалось ровно B уточек. Определите минимальное число уточек, которое могло быть в коллекции Дениса.
Программа получает на вход два целых положительных числа A и B, 2 ≤ A ≤ 2×10⁹, 2 ≤ B ≤ 2×10⁹ – количество уточек при расстановке на полке в первом и во втором случаях.
Программа должна вывести одно число – минимально возможное количество уточек в коллекции Дениса. Гарантируется, что ответ существует и не превосходит 2×10⁹.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 3	11	11 = 5 × 2 + 1 11 = 3 × 4 − 1

Маша любит чётные числа, а Миша – нечётные. Поэтому они всегда радуются, если встречают числа, которые им нравятся.
Сегодня им встретились все целые числа от A до B включительно. Маша решила посчитать сумму всех чётных чисел от A до B, а Миша – сумму всех нечётных, после чего они начали спорить, у кого получилась сумма больше. Помогите им – найдите разность
между суммой Маши и суммой Миши.
Программа получает на вход два целых положительных числа A и B, не превосходящие 2×10⁹.
Программа должна вывести одно число – разность между суммой чётных чисел и суммой нечётных чисел от A до B.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 6	2	Сумма чётных чисел равна 4 + 6 = 10, сумма нечётных чисел равна 3 + 5 = 8, разность равна 2.
2	3 7	-5	Сумма чётных чисел равна 4 + 6 = 10, сумма нечётных чисел равна 3 + 5 + 7 = 15, разность равна −5.

Таня решила позвонить своей подруге, но вспомнила, что та живёт очень далеко, поэтому в часовом поясе подруги может быть слишком поздно или рано. Часы у Тани показывают ровно H часов, Таня живёт в часовом поясе с ними UTC+A, а её подруга – в часовом поясе UTC+B. Помогите Тане определить время в часовом поясе подруги в этот момент.
Программа получает на вход три целых числа H, A и B, 0 ≤ H ≤ 23, −11 ≤ A ≤ 12, −11 ≤ B ≤ 12.

В часовом поясе UTC+A местное время больше, чем время в часовом поясе UTC+0 на A часов (если же A < 0, то меньше на |A| часов). Например, если в часовом поясе UTC+0 сейчас 12 часов, то в часовом поясе UTC+1 – 13 часов, а в часовом поясе UTC−1 – 11 часов. 
Программа должна вывести одно число – время (количество часов) в часовом поясе подруги.
Под временем в этой задаче подразумевается количество часов, которое может принимать значения от 0 до 23. При решении задачи обратите внимание, что в часовом поясе подруги может быть уже следующая дата или предыдущая дата, программа должна вывести количество часов на часах подруги в этот момент, то есть число от 0 до 23.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	15 3 -5	7	У Тани – 15 часов, она живёт в часовом поясе UTC+3. В часовом поясе UTC+0 сейчас 12 часов. Подруга живёт в часовом поясе UTC−5, и у неё сейчас 7 часов.

На шахматной доске размером N × N расставлено N шахматных ладей не бьющих друг друга, то есть на каждой вертикали и каждой горизонтали стоит ровно одна ладья.


Шахматную доску повернули на 90° по часовой стрелке. Выведите получившуюся расстановку ладей.


Входные данные
Первая строка входных данных содержит целое число N, 1 ≤ N ≤ 10⁵ — размер доски. Следующие N строк содержат по одному числу от 1 до N, а именно, в i-й строке записано число a_i — номер вертикали, в которой стоит ладья на i-й горизонтали. В этой задаче горизонтали нумеруются числами от 1 до N сверху вниз, вертикали нумеруются числами от 1 до N слева направо (см.рисунок).

Выходные данные
Программа должна вывести N чисел — расстановку ладей после поворота в таком же формате.

Примеры

№	Входные данные	Выходные данные
1	5 4 2 3 5 1	1 4 3 5 2

Замечание
Пример в условии соответствует рисункам. Первоначально ладьи стояли в столбцах 4, 2, 3, 5, 1
при перечислении их по строкам сверху вниз. После поворота ладьи стоят в столбцах 1, 4, 3, 5, 2.

 

На складе кондитерской фабрики хранятся пирожные двух видов - круассаны и эклеры. Круассанов A штук, а эклеров - B штук. Есть неограниченный запас подарочных коробок, в каждую коробку можно положить только три пирожных. При этом требуется, чтобы в коробке были пирожные обоих видов, то есть в одну коробку можно положить два круассана и один эклер или один круассан и два эклера.
Определите, можно ли упаковать все имеющиеся пирожные в коробки и выведите подходящий способ размещения пирожных по коробкам.


Входные данные
Программа получает на вход два целых числа A и B, записанных в отдельных строках. 1 <= A <= 10⁹, 1 <= B <= 10⁹.

Выходные данные
Если можно разложить все пирожные по коробкам в соответствии с условием задачи, программа должна вывести два целых числа. Первое число равно количеству коробок, в которых лежит два круассана и один эклер. Второе число равно количеству коробок, в которых лежит один круассан и два эклера. 
Если разложить все пирожные по коробкам нужным способом нельзя, программа должна вывести одно число -1.
 

Примеры

№	Входные данные	Выходные данные
1	4 5	1 2
2	5 3	-1

Автобусные остановки расположены через каждые K метров от начала улицы, то есть на расстоянии 0, K, 2K, 3K и т.д. метров от начала. Света прошла от начала улицы N метров, после чего
устала и захотела сесть на автобус. Определите, сколько метров нужно пройти Свете до ближайшей
остановки.

Входные данные
Программа получает на вход два целых числа K и N, записанных в отдельных строках.
1 ≤ K ≤ 2 × 10⁹, 1 ≤ N ≤ 2 × 10⁹

Выходные данные
Программа должна вывести одно целое число — расстояние до ближайшей остановки.
 

Примеры

№	Входные данные	Выходные данные
1	600 2000	200

Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним». Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 – север, 2 – северо-восток, 3 – восток, 4 – юго-восток, 5 – юг, 6 – юго-запад, 7 – запад, 8 – северо-запад) (см. рис). Длина шага в любом направлении равна 1.
    Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).


Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.
 Формат входных данных
    Первая строка  содержит число N – число указаний (1≤N≤40). Последующие N строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.
Формат выходных данных
    Выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось Ox направлена на восток, а ось Oy – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с погрешностью не более 10^-3.
 

Примеры

№	Входные данные	Выходные данные
1	6 1 3 3 1 1 1 3 3 5 2 7 1	3.000 2.000
2	1 8 10	-7.071 7.071

У Индианы Джонса есть ключ от двери, ведущей к тайным богатствам инков. Ключ имеет форму правильного треугольника, который, в свою очередь, разбит на n² маленьких правильных треугольников, в каждом из которых написана одна десятичная цифра. Пример ключа приведен ниже на рисунке.


Джонс вставил треугольник в соответствующее треугольное отверстие в двери, и... она не открылась. Возможно, он вставил ключ неправильно, ведь его можно вставить тремя способами. Из-за того, что у Джонса осталась лишь одна попытка для того, чтоб открыть двери (в случае неудачи его убьют уже настигающие его кровожадные инки), он хочет знать как будет выглядеть ключ при его вставке в дверь другими двумя способами. После этого он сделает правильный выбор. Вас, как одного из двух своих помощников, он попросил показать ему только один из двух возможных вариантов. Внешний вид ключа, приведенного выше, при повороте против и по часовой стрелке изображен на рисунке ниже.


Поскольку вы не хотите смерти Индианы и хотите получить свою долю сокровищ, вам придется помочь ему!

Входные данные
В первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 100). В следующих n строках описан сам треугольник. Строка входного файла, имеющая номер i + 1, содержит 2i - 1 цифру — содержание i-й строки ключа-треугольника.

Последняя строка содержит слово counterclockwise, если треугольник необходимо повернуть против часовой стрелки, и clockwise в противном случае.

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

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 4 5 6 7 8 9 counterclockwise	9  4 8 7  1 3 2 6 5
2	3 1 2 3 4 5 6 7 8 9 clockwise	5  7 6 2  9 8 4 3 1

Как известно, обычно штаны состоят из двух штанин. Однако собачке нужны, например, уже штаны из 5 штанин (для 4-х лап и хвоста), а сороконожке – штаны с 40 штанинами.

У Пети живет Зверь, у которого M лап. Иногда – когда на улице особенно холодно, чтобы Зверь не простудился, на него бывает нужно надеть несколько штанов, чтобы на каждой лапе было надето по несколько штанин.

Петина мама оставила Пете N штанов, имеющих соответственно K₁, K₂, …, K_N штанин, наказав ему надеть на Зверя их все. Петя хочет надеть на Зверя штаны так, чтобы на самой «утепленной» лапе оказалось как можно меньше штанин, но при этом все оставленные мамой штаны были надеты на зверя. Любые штаны можно надевать на любой набор лап (каждая лапа встречается в наборе не более одного раза).

Помогите ему – напишите программу, которая для каждых штанов укажет, на какие лапы должны быть надеты их штанины. Имейте в виду, что две штанины одних и тех же штанов не могут быть надеты на одну и ту же лапу (в то время как штанины разных штанов могут быть надеты на одну и ту же лапу).

Входные данные
Вводится сначала число M, а затем число N (1 ≤ M ≤ 100, 1 ≤ N ≤ 100). Далее вводятся N чисел K_i, обозначающих число штанин у оставленных мамой штанов (1 ≤ K_i ≤ M).

Выходные данные
Выведите N строк, в i-ой строке должно быть выведено Ki различных чисел, обозначающих номера лап Зверя, на которые должны быть надеты штанины i-ых штанов. Лапы Зверя нумеруются натуральными числами от 1 до M. Если искомых ответов несколько, то выведите любой из них.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 3 1 2 3	1 1 2 2 3 4	Первые штаны надеты на лапу 1; вторые штаны надеты на лапы 1 и 2; третьи штаны надеты на лапы 2, 3 и 4. Таким образом, на самых «утепленных» лапах (а это лапы 1 и 2) надето по 2 штанины.
2	4 2 3 2	1 2 3 4 1	Первые штаны надеты на лапы 1, 2 и 3; вторые штаны надеты на лапы 1 и 4. Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2.

Последовательность чисел a1, a2, …, ai,… называется Фибоначчиевой, если для всех i >= 3 верно, что ai = ai–1 + ai–2, то есть каждый член последовательности (начиная с третьего) равен сумме двух предыдущих. Ясно, что задавая различные числа a1 и a2 мы можем получать различные такие последовательности, и любая Фибоначчиева последовательность однозначно задается двумя своими первыми членами.

Будем решать обратную задачу. Вам будет дано число N и два члена последовательности: aN и aN+1. Вам нужно написать программу, которая по их значениям найдет a1 и a2.


Входные данные
Вводятся число N и значения двух членов последователности: aN и aN+1 (1 <= N <= 30, члены последовательности - целые числа, по модулю не превышающие 100).
Если вы пишите на языке программирования Python, то считывание aN и aN+1 элементов должно быть организовано так: 
x, y = map(int, input().split()).

Выходные данные
Выведите два числа — значения первого и второго членов этой последовательности.

Примеры

№	Входные данные	Выходные данные
1	4 3 5	1 1

Маршрут автобуса проходит через N остановок (включая конечные). Отдел по исследованию пассажиропотоков записал данные о том, сколько человек выходило и сколько садилось в автобус на каждой остановке. Напишите программу, которая по этим данным определит, какое максимальное количество человек одновременно в этот рейс ехало в автобусе.

Входные данные
Во входных данных записано сначала число N (2≤N≤100) – количество остановок на маршруте. Далее задается количество человек, севших в автобус на конечной. Далее идет (N-2) пары чисел, задающих для промежуточных остановок количество вышедших и количество вошедших пассажиров. Наконец, идет число, задающее количество вышедших из автобуса на конечной остановке.

Количество вошедших пассажиров на каждой остановке не превышало 100. Данные корректны, в частности, суммарное количество вошедших в автобус на всех остановках пассажиров всегда равно суммарному количеству вышедших.

Выходные данные
Выведите одно целое число — максимальное количество человек, которые в какой-то момент одновременно ехали в автобусе.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 10 3 1 5 10 0 2 15	15	На конечной в автобус село 10 человек. Далее 3 вышло и 1 зашел. В автобусе стало 8 человек. На следующей остановке вышло 5 и зашло 10. Стало 13 человек. На последней промежуточной остановке никто не вышел, а зашло 2 человека. На конечной вышло 15 человек. Итого максимальное количество – 15.
2	5 10 10 0 0 0 0 10 10	10	На конечной село 10 человек, которые на следующей остановке вышли. После этого на следующей остановке никто не сел и никто не вышел. Дальше опять село 10 человек, которые доехали до конечной.
3	5 0  0 9 3 4 2 0 8	10	С конечной автобус отправился без пассажиров. Дальше в него село 9 человек. На следующей остановке 3 вышли и зашли 4. В автобусе стало 10 человек. На следующей остановке 2 вышли и никто не зашел. 8 человек доехало до конечной. Максимальное количество пассажиров составляло 10
4	3 100 0 100 200	200	На начальной и на промежуточной остановку в автобус село по 100 человек. Вышло из автобуса 200 человек.

Вася и Петя играют в следующую игру. Они взяли некоторую последовательность символов и дальше получают из нее новые последовательности, отбрасывая несколько первых символов исходной последовательности (разрешается в том числе не отбрасывать ни одного символа, но не разрешается отбрасывать сразу все символы). Каждый называет по одной такой последовательности. Выигрывает тот, чья последовательность будет идти раньше в алфавитном порядке.

Напомним, что если мы сравниваем две последовательности, и у них первые K символов совпадают, а (K+1)-е символы отличаются, то раньше будет идти по алфавиту та, в которой (K+1)-й символ идет раньше по алфавиту. Если же одна последовательность является началом другой, то раньше по алфавиту идет более короткая из них.

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

Входные данные
В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.

Выходные данные
В выходной файл выведите выигрышную последовательность.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 MAMA	A	Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A
2	4 ALLO	ALLO	Выигрышной является исходная строка
3	5 BBABB	ABB

Рассмотрим N-домино. В таком домино каждая костяшка состоит из двух половинок, на каждой из которых нарисовано от 0 до N точек. Полный комплект костяшек такого домино содержит все возможные костяшки, каждую — по одному разу. Например, для N=2 в комплект войдут следующие костяшки: (0,0), (0,1), (0,2), (1,1), (1,2) и (2,2)

Напишите программу, которая по заданному N определит, сколько всего точек изображено на всех костяшках полного комплекта N-домино.

Входные данные
Вводится натуральное число N (1<=N<=30).

Выходные данные
Программа должна напечатать одно число - общее количество точек на всех костяшках полного комплекта N-домино.

Примеры

№	Входные данные	Выходные данные
1	2	12

На клетчатой бумаге Петя нарисовал отрезок из точки с координатами (a,b) в точку с координатами (c,d). Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через ее внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку).

Входные данные
Вводятся целые числа a, b, c, d. Числа по модулю не превышают 10⁹.

Выходные данные
Выведите одно число — количество клеток, через которые проходит отрезок.

Примеры

№	Входные данные	Выходные данные
1	0 0 6 4	8
2	3 3 -3 3	0

На координатной плоскости расположены равнобедренный прямоугольный треугольник ABC с длиной катета d и точка X. Катеты треугольника лежат на осях координат, а вершины расположены в точках: A (0,0), B (d,0), C (0,d).

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

Входные данные
Сначала вводится натуральное число d(не превосходящее 1000), а затем координаты точки X – два целых числа из диапазона от ­–1000 до 1000.

Выходные данные
Если точка лежит внутри, на стороне треугольника или совпадает с одной из вершин, то выведите число 0. Если точка лежит вне треугольника, то выведите номер вершины треугольника, к которой она расположена ближе всего (1 – к вершине A, 2 – к B, 3 – к C). Если точка расположена на одинаковом расстоянии от двух вершин, выведите ту вершину, номер которой меньше.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1 1	0	Точка лежит внутри треугольника.
2	3 -1 -1	1	Точка лежит вне треугольника и ближе всего к ней вершина A
3	4 4 4	2	Точка лежит на равном расстоянии от вершин B и C,в этом случае нужно вывести ту вершину, у которой номер меньше, т.е. выведено должно быть число 2
4	4 2 2	0	Точка лежит на стороне треугольника.

Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.

Входные данные
Вводится натуральное четырехзначное число.

Выходные данные
Выведите минимальное натуральное  четырехзначное число, состоящее из тех же цифр.

Примеры

№	Входные данные	Выходные данные
1	1513	1135

Секретное агентство «Super-Secret-no» решило для шифрования переписки своих сотрудников использовать «метод бутерброда». Сначала буквы слова нумеруются в таком порядке: первая буква получает номер 1, последняя буква - номер 2, вторая – номер 3, предпоследняя – номер 4, потом третья … и так для всех букв (см. рисунок). Затем все буквы записываются в шифр в порядке своих номеров. В конец зашифрованного слова добавляется знак «диез» (#), который  нельзя использовать в сообщениях.

Например, слово «sandwich» зашифруется в «shacnidw#».



К сожалению, программист «Super-Secret-no», написал только программу шифрования и уволился. И теперь агенты не могут понять, что же они написали друг другу. Помогите им.

Входные данные
Вводится слово, зашифрованное методом бутерброда. Длина слова не превышает 20 букв.

Выходные данные
Выведите расшифрованное слово.

Примеры

№	Входные данные	Выходные данные
1	Aabrrbaacda#	Abracadabra

В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется a минут, второму — b минут, а третьему — c минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени 0, a, 2a, 3a , второй — в моменты времени 0, b, 2b, 3b , а третий в моменты времени 0, c, 2c, 3c .

Момент времени называется подходящим для пересадки , если в этот момент все три автобуса отправляются из столицы Берляндии. Например если a=1, b=2, c=1, то моменты времени 0 и 2 являются подходящими для пересадки, а момент времени 1 не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно t минут. Это означает, что в первый день происходят все моменты времени с 0-го по (t−1)-й включительно, во второй день — c t-го по (2t−1)-й включительно, в третий — с 2t-го по (3t−1)-й включительно и так далее.

Министерство транспорта Берляндии заинтересовалось, сколько подходящих для пересадки моментов времени произойдёт в d-й день в Берляндии. К сожалению, местные чиновники заняты другими делами, поэтому ответить на этот вопрос было поручено вам.

Входные данные
В пяти строках заданы пять целых чисел a, b, c, t  и d (1≤a, b, c≤10⁶ , 1≤t, d≤10⁹ ) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

Выходные данные
Выведите одно целое число — количество подходящих для пересадки моментов времени в d-й день.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	1 2 1 3 1	2	Сутки длятся 3 минуты, поэтому все моменты времени в день с номером 1 — это 0, 1, 2, из них моменты времени 0 и 2 являются подходящими для пересадки
2	2 3 4 7 2	1	Здесь рассматриваются вторые сутки с моментами времени 7, 8, 9, 10, 11, 12, 13. Первый автобус отправляется в моменты времени 8, 10, 12, второй автобус — в моменты времени 9 и 12, а третий — в моменты времени 8 и 12. Таким образом, только момент времени 12 является подходящим для пересадки.
3	2 3 4 3 3	0	Нет ни одного подходящего для пересадки момента времени

Сегодня у Кроша день рождения! По этому поводу он испек огромный торт. Торт представляет собой прямоугольник n × m , разделенный на nm единичных квадратиков горизонтальными и вертикальными линиями из крема.

На праздник в гости к Крошу пришли Совунья и Нюша. По законам гостеприимства, Крош должен поделиться с своим тортом. Для этого он хочет по очереди отрезать от торта два куска и раздать их гостьям.

Отрезать кусок от торта Крош может так: разделить торт на два прямоугольника одним разрезом, проходящим по одной из горизонтальных или вертикальных линий (таким образом, после разреза оба прямоугольника имеют целые длины сторон). Далее, Крош выбирает один из этих прямоугольников и отдает очередной гостье.

После того, как Крош два раза отрежет кусок от своего торта, оставшуюся часть он съедает сам. Сегодня торт получился очень вкусный, и поэтому Крош хочет, чтобы ему достался кусок как можно большей площади. Помогите ему определить, какую максимальную площадь торта он сможет оставить себе.

Входные данные
Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 4·10⁴ ) — длину торта. Вторая строка входных данных содержит единственное целое число m ( 1 ≤ m ≤ 4·10⁴ ) — ширину торта.

Гарантируется, что от торта Кроша можно отрезать два куска, оставив при этом прямоугольник ненулевой площади.

Выходные данные
Выведите одно число — максимальную площадь куска торта, который сможет оставить себе Крош.

Примеры

№	Входные данные	Выходные данные
1	4 3	6

Примечание
Иллюстрация к тесту из примера: Крош делает разрезы вдоль пунктирных линий, отдавая гостьям куски с серыми границами. В конце ему достается кусок размера 2 × 3 .

 

Маше на день рождения подарили набор матрёшек!

Теперь Маша сидит и вкладывает их одну в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки i и j , а их размеры a_i и a_j соответственно, то матрёшка i вкладывается внутрь матрёшки j тогда и только тогда, когда a_i < a_j . Разумеется, непосредственно внутрь матрёшки можно вложить только одну другую матрёшку, иначе получится неаккуратно, а Маша — очень аккуратная девочка.

Маше особенно нравится, если она может, вкладывая матрёшки друг в друга, добиться того, что все они оказываются внутри одной самой большой матрёшки. Но, к сожалению, это не всегда возможно. Поэтому Маша решила убрать часть матрёшек в шкаф, оставив такой набор, чтобы их все можно было вложить друг в друга. Помогите Маше понять, какое максимальное количество матрёшек может быть в таком наборе.

Входные данные
В первой строке находится число n — количество матрёшек, подаренных Маше ( 1 ≤ n ≤ 1000 ). В следующей строке через пробел находятся n чисел — размеры матрёшек. Число a_i , стоящее на месте i , задает размер матрёшки с номером i ( 1 ≤ a_i ≤ 10 000 ).

Выходные данные
Выведите одно число — максимальное количество матрёшек, которые можно вложить друг в друга.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 10 2	2
2	6 2 1 2 1 3 4	4
3	4 3 1 4 2	4