eolymp
bolt
Try our new interface for solving problems
Məsələlər

Квадряд

Квадряд

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Любимая компьютерная игра Мориса называется "Squarow" ("Квадряд"). В начале игры на экране появляется ряд цветных квадратиков. Игрок может выбрать цвет и удалить все квадратики этого цвета (при этом нельзя выбирать цвет, которого нет среди цветов квадратиков). После удаления все оставшиеся квадратики сдвигаются влево так, чтобы в ряду между соседними квадратиками не оставалось пустых мест, порядок квадратиков в ряду при этом не изменяется. Все квадратикиодного цвета, стоящие подряд друг за другом, образуют блок. При удалении выбранного цвета игрок получает столько очков, сколько блоков осталось в ряду.

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

Giriş verilənləri

Первая строка содержит одно целое число n (1n2 * 10^5) - количество квадратиков в ряду. Вторая строка содержит n целых чисел a[i] (1in, 1a[i]2 * 10^5) - цвет i-го квадратика в ряду.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
6
1 1 1 2 2 1
Çıxış verilənləri #1
1 1
Giriş verilənləri #2
12
1 1 2 3 3 3 2 1 1 1 2 2
Çıxış verilənləri #2
4 3
Giriş verilənləri #3
15
4 5 5 4 4 4 5 9 9 5 5 5 5 9 9
Çıxış verilənləri #3
4 4

Qeyd

В первом примере, если удалить цвет 1, останется один блок цвета 2, а если удалить цвет 2, останется один блок цвета 1 (так как блоки по разные стороны от блока цвета 2 сольются в один блок).

Во втором примере, если удалить цвет 1, останется три блока, если удалить цвет 2 - также три блока, если удалить цвет 3, останется 4 блока.

В третьем примере: для цвета 4 - 4 блока, для цвета 5 - 2 блока, для цвета 9 - 4 блока.

Mənbə 2018 Иннополис Первый тур, 1 декабря