C. Почти арифметическая прогрессия
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Гена любит последовательности чисел. Недавно он открыл для себя новый тип последовательностей, который он назвал — почти арифметическая прогрессия. Назовем последовательность почти арифметической прогрессией, если ее элементы можно представить в виде:

  • a1 = p, где p — некоторое целое число;
  • ai = ai - 1 + ( - 1)i + 1·q (i > 1), где q — некоторое целое число.

Сейчас у Гены на листке записана последовательность b, состоящая из n целых чисел. Помогите Гене, найдите в ней самую длинную подпоследовательность чисел, которая является почти арифметической прогрессией.

Последовательность s1,  s2,  ...,  sk называется подпоследовательностью последовательности b1,  b2,  ...,  bn, если найдется такая возрастающая последовательность индексов i1, i2, ..., ik (1  ≤  i1  <  i2  < ...   <  ik  ≤  n), что bij  =  sj. Иными словами, последовательность s может быть получена из b путем вычеркивания некоторых элементов.

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 4000). В следующей строке задано n целых чисел b1, b2, ..., bn (1 ≤ bi ≤ 106).

Выходные данные

Выведите единственное целое число — длину максимальной по длине, искомой подпоследовательности.

Примеры
Входные данные
2
3 5
Выходные данные
2
Входные данные
4
10 20 10 30
Выходные данные
3
Примечание

В первом тесте подходящей подпоследовательностью будет сама последовательность.

Во втором тесте подходит подпоследовательность: 10, 20, 10.