Алгоритмы

Вновь открытое казино предложило оригинальную игру.

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

Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому — на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.

После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.

Требуется написать программу, определяющую максимальную сумму, которую сможет получить игрок.

Входные данные
В первой строке входных данных содержится число K (1 ≤ K ≤ 26) — количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число X_i (1 ≤ X_i ≤ 150, i = 1..K) — цена фишки соответствующего цвета.

В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задаетсяL строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.

В следующей строке содержится число N(1 ≤ N ≤ 150) — количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.

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

Примеры

№	Входные данные	Выходные данные
1	3 v 3 l 1 u 2 luvu 3 luv vul uuu	6

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

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

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

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

Входные данные
Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит 10⁵ символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R - приток впадает в реку с правого берега и B - притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

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

Примечания
Рисунок к приведенному ниже примеру.

Примеры

№	Входные данные	Выходные данные
1	LLBLRRBRL	5

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

Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10) - количество заданных Петей вопросов. Каждая из N последующих строк содержит описание четырех точек - четыре пары целых чисел X и Y (−100 ≤ X ≤ 100, −100 ≤ Y ≤ 100), обозначающих координаты точки.

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

Примеры

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

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

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

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10⁵) - количество папок. Во второй строке записаны N целых чисел a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁵) - количество дипломов в каждой из папок.

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

Примечание
В первом примере Иван может открыть и просмотреть папку 2 за 2 секунды и, не найдя там диплома, понять, что диплом находится в папке 1.

Во втором примере Иван за 2 секунды просмотрит папку 1, потом за 2 секунды просмотрит папку 4, а если ни в одной из них диплома не встретилось, он поймет, что диплом в папке 3.

Примеры

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

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи N одинаковых товаров и получи еще один товар бесплатно"и "купи K товаров по цене K−1 товара".

Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит B рублей. Какое максимальное количество пачек бумаги можно приобрести на A рублей, правильно используя рекламные предложения?

Входные данные
Во входном файле записаны целые числа N, K, A и B (1 ≤ N ≤ 100, 2 ≤ K ≤ 100, 1 ≤ A ≤ 10⁹, 1 ≤ B ≤ 10⁹), разделенные пробелами.

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

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

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры

№	Входные данные	Выходные данные
1	4 4 13 2	8
2	3 4 8 3	2
3	3 4 7 1	9

Алиса и капитан Буран играют в покер с одной картой. Однокарточный покер - это игра для двух игроков с игральными картами. Каждая карта в этой игре показывает целое число от 1 до 13 включительно. Сила карты определяется числом, написанным на ней, следующим образом:
Слабая 2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1 Сильная
В покер с одной картой играют следующим образом:
- Каждый игрок берет одну карту из колоды.
- Выбранная карта становится рукой игрока.
- Игроки раскрывают друг другу руки.
- Игрок с более сильной картой побеждает в игре.
- Если их карты одинаково сильны, игра заканчивается вничью.
Вы смотрите, как Алиса и капитан Буран играют в игру, и можете видеть их руки. Число, написанное на карточке Алисы, - A, а число, написанное на карточке капитана Бурана, - B.

Напишите программу для определения исхода игры.
 

Ушан решил сыграть шестигранным кубиком. На каждой из шести сторон изображено целое число от 1 до 6, а два числа на противоположных сторонах всегда в сумме дают 7. Ушан сначала кладет кубик на стол произвольной стороной вверх, а затем повторно выполняет следующую операцию. Поверните кубик на 90 ° в одном из следующих направлений: влево, вправо, вперед (кубик приблизится) и назад (кубик уйдет дальше), затем получите y очков, где y - это число, написанное на стороне, обращенной вверх.

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

Найдите минимальное количество операций, которое Ушан должен выполнить, чтобы набрать в сумме не менее x баллов.

Входные данные
На вход подается целое число x (\(1<=x<=10^{15}\)).

Выходные данные
Выведите на экран ответ.
 

 

Примеры

№	Входные данные	Выходные данные
1	7	2
2	149696127901	27217477801

 

На линии, идущей с востока на запад, есть N городов. Города пронумерованы от 1 до N в порядке с запада на восток. Каждая точка на линии имеет одномерные координаты, а точка, которая находится дальше на восток, имеет большее значение координаты. Координата города i - Xi. Вы находитесь в городе 1 и хотите посетить все остальные города. У вас есть два способа путешествовать:
- Ходить по линии. Ваш уровень усталости увеличивается на A каждый раз, когда вы путешествуете на расстояние 1, независимо от направления.
- Телепортируйтесь в любое место по вашему выбору. Ваш уровень усталости увеличивается на B независимо от пройденного расстояния.
Найдите минимально возможное общее повышение уровня вашей усталости, когда вы посетите все города этими двумя способами.

Входные данные
В первой строке заданы три целых числа N (\(2<=N<=10^5\)), A (\(1<=A<=10^9\)), B (\(1<=B<=10^9\)). Во второй строке заданы координаты городов Xi (\(1<=X_i<=10^9\)), для всех i \(X_i <X_{i+1}\)(\(1<=i<=N-1\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 2 5 1 2 5 7	11	Из города 1 пройдите расстояние 1 до города 2, затем телепортируйтесь в город 3, затем пройдите расстояние 2 до города 4. Общее увеличение вашего уровня усталости в этом случае составляет 2 × 1 + 5 + 2 × 2 = 11, что является минимально возможным значением.
2	7 1 100 40 43 45 105 108 115 124	84	Из города 1 пройдите пешком до города 7. Общее увеличение вашего уровня усталости в этом случае составляет 84, что является минимально возможным значением.
3	7 1 2 24 35 40 68 72 99 103	12	Посетите все города в любом порядке, телепортировавшись шесть раз. Суммарное повышение уровня утомляемости в этом случае составляет 12, что является минимально возможным значением.

 

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

Входные данные
На вход подается положительное целое число N (\(1<=N<=10^{18}\)).

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

 

Есть N городов. Есть также шоссе K и железные дороги L, проходящие между городами. Каждое i-я шоссе двунаправленно соединяет рi и qi города, а каждая i-я железная дорога двунаправленно соединяет ri и si города. Нет двух шоссе, соединяющих одну и ту же пару городов. Точно так же, никакие две железные дороги не соединяют одну и ту же пару городов. Будем считать, что города A и B соединены шоссе, если до города B можно добраться из города A по некоторому количеству шоссе. Здесь любой город считается соединенным с собой шоссе. Аналогичным образом, мы также определим возможность сообщения железными дорогами. Для каждого города найдите количество городов, соединенных с этим городом как шоссе, так и железными дорогами.

Входные данные
Входные данные поступают в следующем формате:

N K L 
p1 q1 
...
pK qK 
r1 s1 
... 
rl sL

Ограничения:
\(2<=N<=2\cdot10^5 \\ 1<=K,L<=10^5 \\ 1<=p_i,q_i,r_i,s_i<=N\\ p_i <q_i \\ r_i<s_i \\ Когда\ i \neq j, (p_i,q_i)\neq(p_j,q_j) \\ ?Когда\ i \neq j, (r_i,s_i)\neq(r_j,s_j)\)


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

 

Примеры

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

 

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

Входные данные
На вход подается строка s (\(3 <= len(s) <= 10^5\)). Строка состоит только из строчных английских букв (a-z). Никакие два соседних символа в s не равны.

Выходные данные
Если Петя выиграет, выведите First. Если выиграет Ваня, выведите Second.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	aba	Second	Петя не может выполнить операцию, так как удаление символа b, который является единственным символом, который можно удалить, приведет к тому, что s станет равной aa, два одинаковых символа будут соседними.
2	abc	First	Когда Петя удаляет b из s, строка становится равной ac и Ваня не сможет выполнить операцию, поскольку в s нет других символов, за исключением крайних.
3	abcab	First

 

Назовём палиндромом непустую строку, которая читается одинаково справа налево и слева направо. Например, « abcba », « a » и « abba » являются палиндромами, а « abab » и « xy » не являются.

Назовём подстрокой строки строку, полученную отбрасыванием некоторого (возможно, нулевого) количества символов с начала и с конца строки. Например, « abc », « ab » и « c » являются подстроками строки « abc », а « ac » и « d » не являются.

Назовем палиндромностью строки количество её подстрок, которые являются палиндромами. Например, палиндромность строки « aaa » равна 6, так как все её подстроки являются палиндромами, а палиндромность строки « abc » равна 3, так как только подстроки длины 1 являются палиндромами.

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

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 100000) — длина строки s.

Во второй строке задана строка s, состоящая из n строчных букв латинского алфавита.

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

Если подходящих строк несколько, выведите любую.

Примечание
В первом примере у строки « ololo » есть 9 подстрок-палиндромов: « o », « l », « o », « l », « o », « olo », « lol », « olo », « ololo ». Обратите внимание, что некоторые подстроки совпадают, но учитываются несколько раз.

Во втором примере палиндромность строки « abccbaghghghgdfd » равна 29.
 

Примеры

№	Входные данные	Выходные данные
1	5 oolol	ololo
2	16 gagadbcgghhchbdf	abccbaghghghgdfd

В ряд расположены N ящиков. Изначально в i-м ящике слева находится ai конфет.  Громозека выбирает ящик, содержащий хотя бы одну конфету, и съедает одну из конфет в выбранном ящике.Он может выполнять это действие любое количество раз. Его цель добиться того, чтобы в любых двух соседних коробках содержалось не более x конфет.
Найдите минимальное количество операций, необходимых для достижения цели Громозеки.

Входные данные
В первом строке задается два числа N (\(2<=N<=10^5\)) и x (\(0<=x<=10^9\)).  Во второй строке содержится N целых чисел ai (\(0<=a_i<=10^9\)).

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

 

Примеры

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

 

Дана последовательность из N целых чисел (они могут быть положительными, отрицательными или равными 0). Необходимо выбрать из этих чисел два числа так, чтобы их произведение было как можно меньшим (не рассматриваются квадраты данных чисел, но можно выбрать произведение двух различных элементов последовательности, равных друг другу).
В первой строке входных данных записано целое число N, 2 ≤ N ≤10⁵ – количество данных чисел. Следующие N строк содержат сами числа, не превосходящие по модулю 40 000.
Программа должна вывести единственное целое число – наименьшее возможное произведение двух различных элементов этой последовательности.

Примеры

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

В ряд ставятся N кеглей. Громозека красит каждую из них в один из K цветов из своих банок с краской. Из эстетических соображений любые две соседних кегли должны быть окрашены в разные цвета. Найдите количество возможных способов раскрасить кегли.

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).
 

 

Примеры

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

 

Дано число. В этом числе необходимо изменить одну цифру таким образом, чтобы новое число делилось на 3 и было бы максимально возможным. В исходном числе нужно
обязательно изменить одну цифру, даже если исходное число уже делилось на 3. Программа получает на вход одно длинное натуральное число. Длина числа может
достигать 100 цифр.
Программа должна вывести другое натуральное число, удовлетворяющее условиям:
1. Новое число должно отличаться от данного ровно одной цифрой.
2. Новое число должно делиться на 3.
3. Новое число должно быть максимально возможным из всех таких чисел.

Примеры

№	Входные данные	Выходные данные
1	123	723

Володе очень понравились задачи олимпиады по информатике, поэтому он решил ходить на занятия кружка по программированию. Придя на первое занятие кружка, он узнал, что занятия будут проходить еженедельно в один и тот же день недели. Помогите Володе составить календарь занятий до конца года – определите даты всех занятий, начиная с первого занятия и до конца года.
Программа получает на вход два числа, записанных в разных строках: номер месяца и номер дня месяца, когда проходит первое занятие. Номер месяца может быть одним из четырёх возможных чисел – 9, 10, 11, 12. Номер дня месяца – число от 1 до 30 для сентября и ноября (месяцы с номерами 9 и 11) или от 1 до 31 для октября и декабря (месяцы с номерами
10 и 12). 
Программа должна вывести даты всех занятий кружка до конца года в хронологическом порядке, по одной дате в строке, сначала месяц, затем день месяца, через пробел. Занятия проходят еженедельно, в тот же день недели, что и первое занятие. Формат вывода дат такой же, как в условии. Считайте, что каникулы отсутствуют, а последнее занятие может происходить в любой день декабря, в том числе и 31 числа.
 

Примеры

№	Входные данные	Выходные данные
1	11 20	11 20 11 27 12 4 12 11 12 18 12 25

На столе стоят три вазы с конфетами. В левой вазе лежат A конфет, в средней вазе лежат B конфет, в правой вазе лежат C конфет. Лена съедает одну конфету из левой вазы,
затем – одну конфету из средней вазы, затем из правой, средней, левой, средней, правой, средней и т. д. (слева направо, затем налево, опять направо и т.д.)
Если Лена хочет взять конфету из какой-то вазы, а конфет там нет, она расстраивается и идёт спать. Определите, сколько конфет съест Лена.
Программа получает на вход три целых неотрицательных числа A, B, C – количество конфет в левой, средней, правой вазе. Сумма трёх данных чисел не превосходит 2×10⁹.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 3	7	Лена съест конфеты из левой, средней, правой, средней, левой, средней, правой вазы. После этого она захочет съесть конфету из средней вазы, но в ней уже не осталось конфет.

Для выбора водящего в детской игре N человек становятся в круг, после чего произносится считалка. На первом слове считалки указывается на первого человека в кругу, на втором слове – на второго человека и т. д. После N-го человека снова идёт первый человек (все люди в кругу пронумерованы числами от 1 до N, круг зацикливается, после человека с номером N идёт человек с номером 1).
Всего в считалке M слов. Определите, на какого человека придётся последнее слово считалки.
Программа получает на вход два целых положительных числа. Первое число N – количество людей в кругу. Второе число M – количество слов в считалке. Оба числа не превосходят 10⁹.
Программа должна вывести одно целое число от 1 до N – номер человека в кругу на которого придётся последнее слово считалки.

Примеры

№	Входные данные	Выходные данные
1	10 25	5

Для пополнения бюджета в стране Авалон, известной своими горными туристическими маршрутами, ввели новый налог для туристов. Величина налога
пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без
учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению, совершённому туристической группой. Кроме того, в силу старинного обычая все
туристические группы должны перемещаться по горам Авалона строго с запада на восток. Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический
маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным, он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка,
которая находится строго выше начала и конца маршрута. 
Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния. 
Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска.
Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток. Все числа натуральные, не превосходящие 10⁵.
Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего
условиям, не существует, программа должна вывести одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 18 10 15 20 20 10 3	3 6	Дано 7 точек с высотами 18, 10, 15, 20, 20, 10, 3. Самый короткий маршрут, содержащий подъём и спуск, – это 15, 20, 20, 10. Он начинается в точке номер 3 и заканчивается в точке номер 6.
2	3 9 8 5	0	Высота гор монотонно убывает, поэтому искомого маршрута не существует.