Циклы

Мы все знаем, что начавшаяся зима скоро закончится, и на праздновании Масленицы все будут есть блины. Об этом и будет наша задача.

N гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке i-го гостя лежит ai блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из ai.

Неожиданно к ним присоединился ещё один человек, и теперь все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально.

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

Программа получает на вход натуральное число N, не превосходящее 100.000, – первоначальное количество гостей. Следующие N строк содержат натуральные числа a_i – количество блинов на тарелке i-го человека. Значения a_i даны в порядке неубывания, то есть a_i ≤ a_i+1. Сумма значений всех a_i не превосходит 2·10⁹.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 3 5 6	4	За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний – 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов.

На Новом проспекте построили подряд 10 зданий. Каждое здание может быть либо жилым домом, либо магазином, либо офисным зданием.

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

Входные данные
Программа получает на вход десять чисел, разделенных пробелами. Каждое число задает тип здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0 обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом и хотя бы один магазин.

Выходные данные
Выведите одно целое число: наибольшее расстояние от дома до ближайшего к нему магазина. Расстояние между двумя соседними домами считается равным 1 (то есть если два дома стоят рядом, то между ними расстояние 1, если между двумя домами есть еще один дом, то расстояние между ними равно 2 и т.д.)

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 0 1 1 0 1 0 2 1 2	3	В примере из условия дальше всего идти до ближайшего магазина жителям четвертого дома: ближайший к их дому магазин находится в первом доме, и им нужно пройти три дома до него. Жителям других домов придется пройти меньшее расстояние до ближайшего магазина, поэтому ответ 3.

Рассмотрим последовательности чисел. Первая последовательность состоит из одного числа K. Каждая следующая последовательность чисел описывает предыдущую по такому правилу.

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

Например, для K=2 последовательности получатся такими:

№	Последовательность	Как ее читать (слова в описании соответствуют числам текущей последовательности слева направо, и описывают предыдущую последовательность)
1	2	Исходная последовательность
2	1 2	Одна «двойка»
3	1 1 1 2	Одна «единица», одна «двойка»
4	3 1 1 2	Три «единицы», одна «двойка»
5	1 3 2 1 1 2	Одна «тройка», две «единицы», одна «двойка»
6	1 1 1 3 1 2 2 1 1 2	Одна «единица», одна «тройка», одна «двойка», две «единицы», одна «двойка»

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

Входные данные
Вводится число K (1 ≤ K ≤ 9) и число N (1 ≤ N ≤ 15).

Выходные данные
Ваша программа должна печатать N-ую последовательность, полученную из начальной последовательности, состоящей из одного числа K. Числа при выводе следует разделять пробелами.
 

Примеры

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

На контрольной работе N учеников сидят в ряд. Для каждого ученика известно, какую оценку он получил бы, если бы писал эту контрольную самостоятельно (оценка — это число от 2 до 5). Однако ученики могут писать контрольную не только самостоятельно, но и списывать у своего соседа, но только если сосед пишет контрольную самостоятельно. В этом случае списывающий получит такую же оценку, какую получит тот, у кого он списал.

А именно (правила применяются строго в указанном порядке):

• Школьники, которые знают материал на 5, будут писать контрольную самостоятельно.
• Школьник, который знает материал на 4, если он сидит рядом с тем, кто знает на 5, будет списывать у него, а в противном случае будет писать самостоятельно.
• Школьник, который знает на 3, если он сидит рядом с тем, кто знает на 5, будет списывать у него. Если среди его соседей знающего на 5 нет, но есть тот, кто знает на 4, и при этом пишет самостоятельно, то троечник будет списывать у него. В противном случае будет писать самостоятельно.
• Аналогично школьник, знающий на 2 — из соседей, которые пишут самостоятельно, выберет того, кто знает лучше, и спишет у него. А если таких нет (или оба его соседа также знают на 2), то будет писать самостоятельно.

Определите, кто какую оценку в итоге получит.

Входные данные
Вводится число N (1<=N<=10) - количество учеников, и далее последовательность из N чисел, описывающая, кто на какую оценку может написать контрольную, если будет писать самостоятельно.

Выходные данные
Выведите N чисел - оценки, которые получат ученики за контрольную.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 5 2 3 4 5	5 5 3 5 5	Первый и пятый ученики будут писать самостоятельно. Второй спишет у первого, а четвертый — у пятого (в итоге также получат пятерки). Третьему не у кого списывать, так как его соседи будут писать работу не самостоятельно.
2	6 2 2 3 2 2 4	2 3 3 3 4 4	Второй и четвертый спишут у третьего, пятый — у шестого.

В младшей группе детского сада «Телепузики» всего n детей. Каждый из них, как и любой четырехлетка, легко может начать плакать просто из-за того, что его одногруппники тоже плачут. Ну и что, что он не знает, в чем дело? Товарищи же не могут ошибаться.

Воспитательница работает в детском саду уже много лет, и отлично разбирается в детском настроении. Ей достаточно посмотреть на ребенка, чтобы понять, насколько он сегодня плаксив: заплачет ли он сегодня сам из-за того, что компот невкусный, разрыдается ли из-за того, что Катя и Ваня уже плачут, а он еще нет, или же будет сосредоточенно играть c кубиками, не обращая внимание на слезы и сопли товарищей.

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

Входные данные
В первой строке дано целое число n (1n1000) — количество детей в группе. В следующей строке через пробел перечислены n чисел, причем i-е по счету число qi (0qin−1  ) обозначает плаксивость i-го ребенка. Число qi обозначает количество детей, которые должны заплакать, чтобы этот ребенок тоже заплакал. Если qi = 0, значит, этот ребенок точно сегодня заплачет просто так, вне зависимости от своих товарищей. Считается, что ребенок не может начать плакать, если вокруг него не плачет нужное количество детей. Если ребенок начал плакать, то он уже не успокоится до вечера.

Выходные данные
Выведите «YES», если вся группа будет плакать одновременно, или «NO» иначе.

Примеры

№	Входные данные	Выходные данные
1	4 1 0 1 2	YES
2	3 1 1 1	NO

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

Входные данные
В первой строке записаны два числа N и M (1<=M<=N<=1000) – количество домов в Простоквашино и количество тех домов, которые ещё пользуются услугами почтальона Печкина, соответственно. Во второй строке записано M чисел ai , (1<=a_i<=N) возрастающем порядке – номера домов, которые ещё используют бумажную почту.

Выходные данные
В ответ выведите одно число – минимальное количество домов, которое потребуется перенумеровать.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	8 5 1 2 4 5 8	1	В приведенном примере дому, который имел номер 8, нужно дать номер 3. Тогда 5 домов, которые ещё используют бумажную почту, как раз будут иметь номера от 1 до 5.

Артур всегда очень боялся знакомиться с девушками. Дело даже не в природной стеснительности Артура, и даже не столько в том, что Артур не знает, о чем говорить с девушками. Просто Артур с детства не выговаривает букву «р» и очень этого стесняется. Поэтому Артур старается не произносить лишний раз слова, в которых есть эта ненавистная ему буква.

Однажды друзья познакомили Артура с девушкой по имени Нина (о, какое прекрасное имя!). Она была очаровательна и очень болтлива, поэтому Артуру почти не нужно было подбирать слова — она заполняла неловкую тишину за него. Разумеется, он пригласил ее в кафе выпить чашечку кофе. Артур даже продумал все свои реплики заранее: «Счастлив тебя видеть», «Ты сегодня восхитительна», «Да, конечно, я внимательно тебя слушаю», «И что дальше?», «Счет, пожалуйста» и, конечно, «Я позвоню тебе на днях, не скучай».

Но, как известно, не бывает идеальных планов. Все шло как по маслу, но вдруг, сидя за столиком в кафе, Нина сказала, что ужасно не выспалась и не отказалась бы от N чашек кофе. И тут Артур понял, что он не обдумал заранее, как он будет делать заказ. Понятно, что нужно сказать что-то вроде: «Сколько-то чашек кофе, пожалуйста», но вот сколько же чашек нужно, чтобы Нина так и не поняла, что Артур не выговаривает букву «р»? Явно нужно заказать не меньше, чем N + 1 чашку — чтобы и Нине досталось N чашек, и самому выпить, но вот сколько точно — Артур не знает. Денег у него не слишком много, поэтому заказывать больше, чем жизненно необходимо для того, чтобы избежать разоблачения, Артур не хочет.

Помогите Артуру — посчитайте, сколько чашек кофе он должен заказать.

Входные данные
Вводится одно целое число N (1 ≤ N ≤ 2999).

Выходные данные
Выведите одно число — количество чашек кофе, которое должен заказать Артур.

Примеры

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

У Славы очень много друзей, и ему очень нравится с ними встречаться. Но, к сожалению, все друзья Славы живут в разных городах (каждый в своем), до которых Слава из своего Большого Города может добраться только на электричках. Каждый раз, когда Слава решает навестить кого-нибудь из своих друзей, перед ним встает нелегкий выбор — к кому же именно поехать на этот раз. Всех своих друзей Слава очень любит и не хочет никого обидеть. Поэтому он поступает следующим образом: в некоторый момент времени Слава выходит из дома и едет на вокзал. После приезда на вокзал Слава садится в ближайшую электричку, которая едет к одному из его друзей. По известному времени приезда Славы на вокзал помогите ему узнать, к какому именно другу он сегодня поедет.

Входные данные
В первой строке входных данных содержатся числа M (1 ≤ M ≤ 10⁵) — количество электричек, которые отправляются с вокзала, и время T, в которое Слава приезжает на вокзал (0 ≤ T ≤ 10⁹). Далее следует M строк, в каждой из которых содержится два числа t_i (0 ≤ t_i ≤ 10⁹, все ti различны) и fi (1 ≤ f_i ≤ 10⁹), где t_i — время отправления i-й электрички(все t_i различны), а f_i соответствует номеру друга, к которому идет i-я электричка. Гарантируется, что есть хотя бы одна электричка, которая отправляется позже, чем момент времени T.

Выходные данные
Выведите одно число — номер друга, к которому сегодня поедет Слава.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 74 28 3 85 2 6 1 5 3 72 1	2	Считается, что Слава успевает на i-ю электричку только в том случае, если он приезжает раньше момента её отправления, т. е. T < ti.

После многих лет медитации один монах дзен понял, что в действительности еще не просветлен. Придя к мастеру, он спросил, как достичь просветления. Мастер же ответил ему: «Даже мастера не знают этого». Когда же монах недоуменно переспросил его, мастер сказал ему, что есть люди, которые кажутся просветленными, а на самом деле глупы и ничего не понимают в дзен. В качестве иллюстрации своих слов он предложил ему следующую задачу.

Человека можно представить в виде таблицы размера N × M, заполненной некоторыми целыми числами. Сумма чисел в строке таблицы символизирует то, каким человека видят люди (чем больше сумма, тем более просветленным в этой области дзен считается человек). Сумма чисел в столбце символизирует реальные познания человека (чем она меньше, тем меньше человек знает, причем если сумма чисел отрицательна, то представления человека ложны). Нужно заполнить таблицу любыми целыми числами так, чтобы сумма чисел в каждой строке таблицы была положительной (то есть человек внешне казался абсолютно просветленным), а сумма чисел в как можно большем количестве столбцов была отрицательной (то есть представления человека о дзен на самом деле были по большей части ложными).

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

Входные данные
Вводятся числа N (1 ≤ N ≤ 100) и M (1 ≤ M ≤ 100) — количество строк и столбцов в таблице. Числа разделены пробелом.

Выходные данные
Сначала выведите максимальное для данных размеров таблицы количество столбцов, сумма чисел в которых отрицательна, а затем и саму заполненную соответствующим образом таблицу. Если существует несколько способов заполнить таблицу, выведите любой из них. Числа в ответе не должны превосходить 1000.

Примеры

№	Входные данные	Выходные данные
1	3 4	3 8 13 -40 21 -17 -4 18 12 6 -10 13 -5
2	3 5	4 1 2 3 4 5 5 4 3 2 1 -7 -8 -7 -8 40

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

Каждый игрок похвастал, сколько у него тузов. Определите, сколько игроков заведомо солгали.

Например, они сказали 1, 1, 1, 2. Следовательно, заведомо солгал 1 игрок. (Какие-то трое могли сказать правду, но все четверо правду сказать не могли, так как тузов всего 4).

Входные данные
Вводятся 4 числа (от 0 до 9 каждое), разделенных пробелом – количество тузов по словам первого, второго, третьего и четвертого игроков.

Выходные данные
Выведите одно число – минимальное количество игроков, которые заведомо солгали. Если все одновременно могли сказать правду, выведите число 0.

Примеры

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

Известно, что в Китайском календаре года следуют 12-летнему циклу: Ox(Бык), Tiger(Тигр), Rabbit(Кролик), Dragon(Дракон), Snake(Змея), Horse(Лошадь), Goat(Коза), Monkey(Обезьяна), Rooster(Петух), Dog(Собака), Pig(Свинья), Rat(Крыса), и затем Ox опять. 
Уже много лет корова Беси гордится, что она родилась в год Быка. Её подружка Эльза хочет узнать сколько лет отделяет её рождение от рождения Беси и надеется, что вы поможете ей узнать это, основываясь на отношениях между датами рождения некоторых коров на ферме.

Входные данные
Первая строка ввода содержит целое число N (\(1<=N<=100\)). Каждая из следующих N строк содержит 8-словную фразу указывающую отношение между датами рождения двух коров. В следующей форме

"Mildred born in previous Dragon year from Bessie",

или

"Mildred born in next Dragon year from Bessie" (previous - предыдуший, next-следующий).

Последнее слово - имя коровы, которое или Bessie или корова ранее упомянутая в предыдущей строке ввода.
Первое слово - имя коровы, которая не Bessie и ещё не упоминалась на вводе. Все имена коров имеют не более 10 символов a..z или A..Z.

5-ое слово - один из знаков зодиака, указаных ранее.

4-ое слово либо "previous" либо "next". Например, фраза "Mildred born in previous Dragon year from Bessie", означает, что год рождения Mildred был год Дракона(Dragon), ближайший и строго раньше (не равен) года рождения Беси.

Выходные данные
Выведите количество лет, на которое отличаются дни рождения Беси и Эльзы. Гарантируется, что это число может быть определено из введённых данных.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	4 Mildred born in previous Dragon year from Bessie Gretta born in previous Monkey year from Mildred Elsie born in next Ox year from Gretta Paulina born in next Dog year from Bessie	12	В примере выше Elsie родилась на 12 лет раньше Bessie. Mildred родилась на 9 лет раньше Bessie. Gretta родилась на 17 лет раньше Bessie. Paulina родилась на 9 лет раньше Bessie.

Напишите программу, которая в последовательности целых чисел определяет значение наименьшего числа из всех четных введенных чисел. Программа получает на вход целые положительные числа, количество введенных чисел неизвестно, последовательность чисел заканчивается числом 0 (0-признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 1000. Введенные числа не превышают 30 000.  Среди  введенных чисел есть хотя бы одно четное
Программа должна вывести одно число: наименьшее из всех четных введенных чисел

Пример работы программы

Напишите программу, которая в последовательности целых чисел определяет сумму четных чисел, принадлежащих интервалу (15,190). Программа получает на вход целые числа, количество введенных чисел неизвестно, последовательность чисел заканчивается числом 0 (0-признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 1000. Введенные числа по модулю не превышают 30 000.
Программа должна вывести одно число: сумму четных чисел, принадлежащих интервалу (15,190).

Пример работы программы

Напишите программу, которая в последовательности целых чисел определяет сумму двузначных нечетных чисел. Программа получает на вход целые числа, количество введенных чисел неизвестно, последовательность чисел заканчивается числом 0 (0-признак окончания ввода, не входит в последовательность).
Количество чисел не превышает 1000. Введенные числа по модулю не превышают 30 000.
Программа должна вывести одно число: сумму двузначных нечетных чисел.

Пример работы программы

Джоан Роулинг, Гарри Поттер и актер Дэниел Рэдклифф все родились в один день – 31 июля. Одно из любимых времен года - зима

Уставшие от необычно теплой зимы, жители Хогвартса решили узнать, действительно ли это самая длинная оттепель за всю историю наблюдений за погодой. Они обратились к синоптикам, а те, в свою очередь, занялись исследованиями статистики за прошлые годы. Их интересует, сколько дней длилась самая длинная оттепель.

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

Входные данные: Cначала вводится число N – общее количество рассматриваемых дней (1 <= N <= 100).
В следующих N строках задается по одному целому числу. Каждое число – среднесуточная температура в соответствующий день. Температуры – целые числа, принадлежащие диапазону от –50 до 50.

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

Пояснения к примерам:

1) Рассматриваются 6 дней. Самая продолжительная оттепель была на 4-й и 5-й день (50 и 10 градусов соответственно)
2) Самая продолжительная оттепель была в первые 4 дня
3) Дней с положительной температурой не было

Примеры

№	Входные данные	Выходные данные
1	6 -20 30 -40 50 10 -10	2
2	8 10 20 30 1 -10 1 2 3	4
3	5 -10 0 -10 0 -10	0

«Ночной рыцарь» – автобус для ведьм и волшебников, попавших в трудное положение. 
«Ночной рыцарь» поражает своими размерами. Небольшой по длине, в высоту он значителен. Гигантские колеса, три этажа. Цвет машины – ярко-фиолетовый.
Автобус обладает несколькими волшебными свойствами. Во-первых, он возникает тут же, по первому требованию, в любом месте и в любое время. Волшебнику даже не приходится ждать. Оборудованные остановки «Ночному рыцарю» не нужны. Примеры

№	Входные данные	Выходные данные
1	1 927	No crash
2	3 763 545 113	Crash 3

На прямой тропинке на расстоянии 1 метр друг от друга сидят два кузнечика. Время от времени один из кузнечиков прыгает на несколько сантиметров влево или вправо. Требуется узнать, каково было минимальное расстояние, на которое сближались кузнечики в процессе прыжков. (Расстояние считается только в те моменты, когда оба кузнечика сидят на земле).

Входные данные: В первой строке вводится одно число N (1 <= N <= 100) – общее количество прыжков, а затем N чисел, описывающих прыжки. Модуль числа равен длине прыжка в сантиметрах; число отрицательное, если кузнечик начинал этот прыжок по направлению к другому кузнечику, и положительное – если от другого кузнечика. Числа по модулю не превосходят 100 и все отличны от 0. (Кузнечики могут перепрыгивать друг через друга. Гарантируется, что кузнечики не приземляются друг на друга.)

Выходные данные: Требуется вывести одно число – минимальное расстояние в сантиметрах, на которое сближались кузнечики.

Примеры

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

Вася записывает в клетки квадратной таблицы NxN натуральные числа по порядку, сначала заполняя первую строку слева направо, затем вторую и т.д. (см. рисунок слева). Петя заполняет такую же таблицу, расставляя числа сначала в первый столбец сверху вниз, затем во второй столбец и т.д.

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

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

Входные данные 
Вводится одно число - размер таблицы.

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

Размер таблицы - натуральное число, не превосходящее 100.

Примеры

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

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

Числа, следующие за числом 0, считывать не нужно.

Входные данные: Дана последовательность натуральных чисел, завершающаяся число 0.

Выходные данные: Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	1 7 7 8 1 0	2

Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами A, B и C (A < B < C) сидят три кузнечика, которые играют в чехарду по следующим правилам:
1. На одной плитке может находиться только один кузнечик.
2. За один ход один из двух крайних кузнечиков (то есть с плитки A или с плитки C) может перепрыгнуть через среднего кузнечика (плитка B) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между B и C или A и B соответственно). Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.
Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).
Даны три числа: A, B, C. Определите, какое наибольшее число ходов может продолжаться игра.

Формат входных данных
Программа получает на вход три целых числа A, B и C (1 <= A < B < C <= 1000), записанных в отдельных строках.
Формат выходных данных
Выведите одно число — наибольшее количество ходов, которое может продолжаться игра.
 

Ввод	Вывод	Примечание
1 4 6	2	В примере сначала кузнечик с плитки №6 прыгает на плитку №3. Затем кузнечик с плитки №4 прыгает на плитку №2.