Задача 4. Неисправный робот

Автор:Иван Кобец   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

Формат входных данных

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

Во второй строке записано n целых чисел ai - показания датчика.

Формат выходных данных

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

Ограничения

4 ≤ n ≤ 2000

1 ≤ ai ≤ 100

Система оценки и описание подзадач

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
n
1204 ≤ n ≤ 10полная
2304 ≤ n ≤ 1001полная
3504 ≤ n ≤ 20001, 2полная

Пояснение к примеру

В примере, робот при старте сделал замер 2 метра. Затем робот, проехав первую секунду, сделал замер 4. Далее робот делает разворот 1 секунду, после делает замер 4. Спустя следующую секунду робот возвращается в стартовую точку, делая контрольный замер в 2 метра. Итого робот проехал 3 секунды.

Примеры тестов

Стандартный вход Стандартный выход
1
6
2 3 4 5 4 2
3

0.164s 0.035s 15