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

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

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

Последовательность s₁,  s₂,  ...,  s_k называется подпоследовательностью последовательности b₁,  b₂,  ...,  b_n, если найдется такая возрастающая последовательность индексов i₁, i₂, ..., i_k (1  ≤  i₁  <  i₂  < ...   <  i_k  ≤  n), что b_ij  =  s_j. Иными словами, последовательность s может быть получена из b путем вычеркивания некоторых элементов.