Квадрядок#8644

Квадрядок

1 секунда

128 мегабайтів

Легка

Улюблена комп'ютерна гра Моріса називається Squarow (Квадряд). На початку гри на екрані з'являється рядок кольорових квадратиків. Гравець може вибрати колір і видалити всі квадратики цього кольору (при цьому не можна вибирати колір, якого немає серед кольорів квадратиків). Після видалення всі інші квадратики зсуваються вліво так, щоб у рядку між сусідніми квадратиками не залишалося порожніх місць, порядок квадратиків у рядку при цьому не змінюється. Всі квадратики одного кольору, що стоять підряд один за одним, утворюють блок. При видаленні вибраного кольору гравець отримує стільки очок, скільки блоків залишилося в рядку.

Допоможіть Морісу дізнатися, яке найбільше число блоків після видалення квадратиків одного кольору він може отримати, і який колір для цього треба вибрати. Якщо таких кольорів декілька, виведіть будь-який.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \leq n \leq 2 \cdot 10^{5}) — кількість квадратиків у рядку. Другий рядок містить $n$ цілих чисел $a_{i}$ a_i ( $1 \leq i \leq n$ 1 \leq i \leq n, $1 \leq a_{i} \leq 2 \cdot 1 0^{5}$ 1 \leq a_i \leq 2 \cdot 10^{5}) — колір $i$ -го квадратика в рядку.

Вихідні дані

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

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі, якщо видалити колір $1$ , залишиться один блок кольору $2$ , а якщо видалити колір $2$ , залишиться один блок кольору $1$ (оскільки блоки по різні сторони від блоку кольору $2$ зіллються в один блок).

У другому прикладі, якщо видалити колір $1$ , залишиться три блоки, якщо видалити колір $2$ — також три блоки, якщо видалити колір $3$ , залишиться $4$ блоки.

У третьому прикладі: для кольору $4$ — $4$ блоки, для кольору $5$ — $2$ блоки, для кольору $9$ — $4$ блоки.