Ост19

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

Итак, на длинной скамейке - N потрёпанных жизнью лицеистов. Чем бы поднять настроение?
- Ой, у меня оба соседа с одинаковыми именами! Могу желание загадывать!
- А давайте поменяем правила: загадывать желание может тот, у кого слева и справа есть люди с совпадающими именами. И желание можно загадывать под каждую пару лицеистов с одинаковыми именами, один из которых слева, а другой справа.
- Тогда нам стоит пересеть, чтобы загадывать побольше желаний!

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

Например, если лицеистов пятеро и зовут их Андрей, Андрей, Андрей, Илья и Олег, они могут загадать 5 желаний. Для этого им нужно сесть, например, так: Андрей-1, Илья, Олег, Андрей-2, Андрей-3. Тогда Илья и Олег смогут загадать по 2 желания каждый, поскольку сидят между Андреем-1 и Андреем-2 и между Андреем-1 и Андреем-3, и ещё одно желание сможе заадать Андрей-2 (он между Андреем-1 и Андреем-3)

Входные данные: В первой строке - натуральное число N, не превышающее 100 - количество лицеистов на скамейке. В последующих N строках - имена лицеистов (пусть это будут строки из букв латиницы длиной не более 50 символов).

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