Problem Almost Arithmetical Progression

Link: http://codeforces.com/problemset/problem/255/C

C. Almost Arithmetical Progression

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Gena loves sequences of numbers. Recently, he has discovered a new type of sequences which he called an almost arithmetical progression. A sequence is an almost arithmetical progression, if its elements can be represented as:

• a₁ = p, where p is some integer;
• a_i = a_i - 1 + ( - 1)^i + 1·q (i > 1), where q is some integer.

Right now Gena has a piece of paper with sequence b, consisting of n integers. Help Gena, find there the longest subsequence of integers that is an almost arithmetical progression.

Sequence s₁,  s₂,  ...,  s_k is a subsequence of sequence b₁,  b₂,  ...,  b_n, if there is such increasing sequence of indexes i₁, i₂, ..., i_k (1  ≤  i₁  <  i₂  < ...   <  i_k  ≤  n), that b_ij  =  s_j. In other words, sequence scan be obtained from b by crossing out some elements.

Input

The first line contains integer n (1 ≤ n ≤ 4000). The next line contains n integers b₁, b₂, ..., b_n (1 ≤ b_i ≤ 10⁶).

Output

Print a single integer — the length of the required longest subsequence.

Sample test(s)

input

2
3 5

output

2

input

4
10 20 10 30

output

3

Note

In the first test the sequence actually is the suitable subsequence.

In the second test the following subsequence fits: 10, 20, 10.

Thuật toán: Quy hoạc động.
Gọi f[i,j] là kết quả khi xét từ đoạn i..j.
Nếu có a[j] trước a[i]: f[i][j] = f[pos[a[j]]][i] + 1.
Nếu chưa có a[j] nào trước a[i] thì f[i][j] = 2.
Đánh dấu a[i].

Code:

/*
Coder : Nguyen Duc Tam
template for contest
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<cctype>

using namespace std;

/*
define for statement loop
*/
#define REP(i, start, end, step) for(int i = start; i < end; i += step)
#define DOWN(i, start, end, step) for(int i = start; i > end; i -= step)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

/*
define operator bit
*/
#define L(x,i) ((x) << (i))
#define R(x,i) ((x) >> (i))
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a) | (b))
#define XOR(a,b) ((a) ^ (b))
#define NOT(a) (~(a))
#define SB(x,i) (OR((x), L(1, (i)))) // x | 1 << i
#define CB(x,i) (AND((x),NOT(L(1,(i))))) // x & ~(1 << i)
#define TB(x,i) (AND((x), L(1,(i)))) // x & (1 << i)

/*
define init data
*/
#define FILL(a,val) memset(a,val,sizeof(a));
#define INIT(a,l,r,val) REP(i,l,r,1) (a)[i] = val;

/*
define convert data
*/
#define DIG(c) (int)((c) - '0')
#define CHR(c) (char)((c) + '0')
#define LOW(c) (char)((c) + 32)
#define UPP(c) (char)((c) - 32)

/*
define math function
*/
#define sqr(a) (a) * (a)
#define abs(a) (a < 0 ? -(a) : (a))

/*
define find element in container very fast.
*/
#define LO(c,x) lower_bound(ALL(c),x)
#define UP(c,x) upper_bound(ALL(c),x)
#define IOF(c,x) distance((c).begin(), LO((c),x))
#define IOL(c,x) distance((c).begin(), UP((c),x))
#define IN(c,x) binary_search(ALL(c),x)
#define ER(c,x) equal_range(ALL(c),x)

/*
define geo
*/
#define DIS(p,q) sqrt(sqr(p.x - q.x) + sqr(p.y - q.y)) // khoang cach Euclide
#define DIM(p,q) abs(p.x - q.x) + abs(p.y - q.y) // khoang cach mahatan


/*
define constant
*/

#define EPS 1e-7
#define OO 1000000005
#define N 4005

#define X first
#define Y second

struct Point
{
double x, y;
Point(){}
Point(double x,double y):x(x), y(y){}
};

struct Node
{
int value;
Node* next;
Node(){}
Node(int value, Node* next):value(value),next(next){}
};

struct Edge
{
int src, dst, weight;
Edge(){}
Edge(int src, int dst, int weight):src(src), dst(dst), weight(weight){}

};

struct Compare
{

bool operator() (const int i, const int j)
{
return i > j;
}

/*
bool operator() (const Point& p, const Point& q)
{
return (p.x != q.x ? p.x < q.x : p.y < q.y);
}
*/
/*
bool operator()(const Edge& e, const Edge& f)
{
return (e.weight != f.weight ? e.weight > f.weight : e.src != f.src ?
e.src < f.src : e.dst < f.dst); // inverse weight
}
*/
};


const int DAY[13] = {-1,31,29,31,30,31,30,31,31,30,31,30,31};

const int dx4[4] = {-1, 0, 1, 0}; //U - R - D - L
const int dy4[4] = {0, 1, 0, -1};

const int dx8[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; //U - UR - R - DR - D - DL - L - UL
const int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

typedef pair<int,int> II;
typedef pair<II,int> III;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned char UC;

vector<int>::iterator it, low, up; // using lower_bound, upper_bound
pair<vector<int>::iterator, vector<int>::iterator > bound; // using function equal_range(first, last, x)
Compare comp;
Point p[2];

int n, a[N], res = 0, temp = 0, f[N][N], pos[1000005];

int main()
{
#define Off  true
if(Off)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
cin >> n;
REP(i,0,n,1)
{
scanf("%d",&a[i]);
}
REP(j,1,n,1)
{
REP(i,0,n,1) pos[a[i]] = -1;
REP(i,0,j,1)
{
if(pos[a[j]] >= 0)
f[i][j] = f[pos[a[j]]][i] + 1;
else
f[i][j] = 2;
pos[a[i]] = i;
}
}
res = 1;
REP(i,0,n,1)
REP(j,i + 1,n,1)
res = max(res,f[i][j]);
cout << res << endl;
return 0;
}