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

Условие

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

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

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

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

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

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

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

Ограничения

4 ≤ n ≤ 2000

1 ≤ a_i ≤ 100

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

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

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

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

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

6
2 3 4 5 4 2

3