Задача №113357. Планета Бублик
На планете Бублик идёт война. Каждый из городов планеты принадлежит одному из нескольких враждующих государств. На планете есть n городов, расположенных вокруг дырки от Бублика и пронумерованных числами от 1 до n в порядке их обхода по кругу. Расстояние между любыми двумя соседними по кругу городами (в том числе между городом номер n и городом номер 1 ) одно и то же, а именно 42 бубликанских километра.
Когда на какой-то город происходит нападение, из него в противоположных направлениях выбегают два гонца. Двигаясь с одинаковой постоянной скоростью, они пробегают полный круг, предупреждая о нападении все города этого государства на своём пути. Чем больше максимальное время, которое пройдёт между нападением на какой-то город государства и моментом, когда все города этого государства будут оповещены о нападении, тем более уязвимым является данное государство. Вы решили выбрать наиболее уязвимое государство и предупредить его об опасности.
Вам дана политическая карта планеты Бублик. Требуется найти два города, принадлежащих одному государству, расстояние между которыми максимально.
В первой строке содержится единственное число n ( 2 ≤ n ≤ 1000 ) — количество городов.
Во второй строке содержатся n чисел, i -е из которых — номер государства, владеющего i -м городом. Номера всех государств — целые числа от 1 до 10 9 включительно.
Гарантируется, что найдутся хотя бы два города, принадлежащие одному государству.
Выведите номера двух различных городов, принадлежащих одному государству, расстояние между которыми максимально. Если правильных ответов несколько, разрешается вывести любой из них.
В первом примере первый и четвёртый города принадлежат государству 1 , а расстояние между ними составляет 126 бубликанских километров, тогда как расстояния между городами 3 и 5 и городами 2 и 6 составляют 84 бубликанских километра.
Во втором примере расстояние между вторым и шестым городом равно 126 бубликанских километров.
7 1 2 3 1 3 10 2
1 4
7 30 40 10 40 10 40 20
2 6