255C.md (1667B)
1 Source: https://codeforces.com/problemset/problem/255/C 2 3 C. Almost Arithmetical Progression 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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: 22 23 * *a*1 = *p*, where *p* is some integer; 24 * *a**i* = *a**i* - 1 + ( - 1)*i* + 1·*q* (*i* > 1), where *q* is some integer. 25 26 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. 27 28 Sequence *s*1, *s*2, ..., *s**k* is a subsequence of sequence *b*1, *b*2, ..., *b**n*, if there is such increasing sequence of indexes *i*1, *i*2, ..., *i**k* (1 ≤ *i*1 < *i*2 < ... < *i**k* ≤ *n*), that *b**i**j* = *s**j*. In other words, sequence *s* can be obtained from *b* by crossing out some elements. 29 30 Input 31 32 The first line contains integer *n* (1 ≤ *n* ≤ 4000). The next line contains *n* integers *b*1, *b*2, ..., *b**n* (1 ≤ *b**i* ≤ 106). 33 34 Output 35 36 Print a single integer — the length of the required longest subsequence. 37 38 Examples 39 40 Input 41 42 ``` 43 2 44 3 5 45 ``` 46 47 Output 48 49 ``` 50 2 51 ``` 52 53 Input 54 55 ``` 56 4 57 10 20 10 30 58 ``` 59 60 Output 61 62 ``` 63 3 64 ``` 65 66 Note 67 68 In the first test the sequence actually is the suitable subsequence. 69 70 In the second test the following subsequence fits: 10, 20, 10.