## Editorial for Đoạn cao trào của bản nhạc

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

var n,re:integer;
a,b,c:array[1..5000] of integer;

procedure rf;
var i:integer; j,k:integer;
begin
for i:=1 to n do
begin
end;
end;

procedure pr;
var i,j,t:integer;
begin
re:=0;
for i:=2 to n do
begin
fillchar(c,sizeof(c),0);
for j:=0 to n-1 do
begin
t:=i+j;
if t>n then break;
b[j+1]:=a[t];
if (j>0) and (b[j+1]-a[j+1]=b[j]-a[j]) then
begin
c[j+1]:=c[j]+1;
if c[j+1]>re then
begin
re:=c[j+1];
if re+1>=i-1 then break;
end;
end;
end;
end;
end;

procedure wf;
begin
if re+1>=5 then write(re+1)
else write(0);
end;

begin
rf;
pr;
wf;
end.


program theme;
uses    math;
const   fi='';
maxN=5001;
var     n,res:longint;

a:array[1..maxN] of longint;
f:array[1..maxN,1..maxN] of longint;

procedure input;
var     inp:text;
i:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
close(inp);
end;

procedure dp;
var     i,j:longint;
begin
for j:=1 to n do f[1,j]:=1;
for i:=2 to n-1 do
for j:=i+2 to n do
begin
if (a[i]-a[i-1])=(a[j]-a[j-1]) then
begin
f[i,j]:=f[i-1,j-1]+1;
res:=max(res,min(f[i,j],j-i));
end
else
f[i,j]:=1;
end;
end;

begin
input;
dp;
if res<5 then res:=0;
write(res);
end.


#### Code mẫu của RR

{\$R+,Q+}
PROGRAM THEME;
CONST
FINP='';
FOUT='';
maxn=5000;
VAR
d:array[1..maxn,1..maxn] of integer;
c:array[1..maxn] of integer;
n,kq:integer;
var
f:text;
i:integer;
begin
assign(f,FINP); reset(f);
for i:=1 to n do
for i:=1 to n-1 do
c[i]:=c[i+1]-c[i];
close(f);
end;
procedure writeOutput;
var
f:text;
begin
assign(f,FOUT); rewrite(f);
if kq+1>4 then writeln(f,kq+1)
else writeln(f,0);
close(f);
end;
procedure solve;
var
i,j:integer;
begin
kq:=0;
for j:=n-1 downto 1 do
if c[j]=c[n] then d[n,j]:=1 else d[n,j]:=0;
for i:=n-1 downto 2 do
for j:=i-kq-2 downto 1 do
if c[i]=c[j] then
begin
d[i,j]:=d[i+1,j+1]+1;
if d[i,j]>kq then kq:=d[i,j];
end
else d[i,j]:=0;
end;
BEGIN
solve;
writeOutput;
END.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int min(int a,int b)
{
if(a>b) return b;
else return a;
}

int main()
{
// freopen("NKTHEME.inp","r",stdin);
int n,x,y,a[5001];
scanf("%d",&n);
for(int i = 1;i<=n;i++)
{
scanf("%d",&x);
if(i>=2)
a[i-1]=x-y;
y = x;
}
int max = 0;
n--;
int f[n+1][n+1];
for(int i =0;i<=n;i++)
f[0][i]=0;
for(int i = 1;i<=n-4;i++)
for(int j = i+4;j<=n;j++)
{
if(a[i] == a[j])
{
f[i][j] = min(f[i-1][j-1]+1,j-i-1);
}
else f[i][j]=0;
if(f[i][j]>max)
max = f[i][j];
}
if(max >= 4) printf("%d",max+1);
else printf("0");
//  getch();
}


#### Code mẫu của khuc_tuan

inline bool leq(int a1, int a2,   int b1, int b2) { // lexic. order for pairs
return(a1 < b1 || a1 == b1 && a2 <= b2);
}                                                   // and triples
inline bool leq(int a1, int a2, int a3,   int b1, int b2, int b3) {
return(a1 < b1 || a1 == b1 && leq(a2,a3, b2,b3));
}
// stably sort a[0..n-1] to b[0..n-1] with keys in 0..K from r
static void radixPass(int* a, int* b, int* r, int n, int K)
{ // count occurrences
int* c = new int[K + 1];                          // counter array
for (int i = 0;  i <= K;  i++) c[i] = 0;         // reset counters
for (int i = 0;  i < n;  i++) c[r[a[i]]]++;    // count occurences
for (int i = 0, sum = 0;  i <= K;  i++) { // exclusive prefix sums
int t = c[i];  c[i] = sum;  sum += t;
}
for (int i = 0;  i < n;  i++) b[c[r[a[i]]]++] = a[i];      // sort
delete [] c;
}

// find the suffix array SA of s[0..n-1] in {1..K}^n
// require s[n]=s[n+1]=s[n+2]=0, n>=2
void suffixArray(int* s, int* SA, int n, int K) {
int n0=(n+2)/3, n1=(n+1)/3, n2=n/3, n02=n0+n2;
int* s12  = new int[n02 + 3];  s12[n02]= s12[n02+1]= s12[n02+2]=0;
int* SA12 = new int[n02 + 3]; SA12[n02]=SA12[n02+1]=SA12[n02+2]=0;
int* s0   = new int[n0];
int* SA0  = new int[n0];

// generate positions of mod 1 and mod  2 suffixes
// the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
for (int i=0, j=0;  i < n+(n0-n1);  i++) if (i%3 != 0) s12[j++] = i;

// lsb radix sort the mod 1 and mod 2 triples
radixPass(s12 , SA12, s+2, n02, K);
radixPass(SA12, s12 , s+1, n02, K);
radixPass(s12 , SA12, s  , n02, K);

// find lexicographic names of triples
int name = 0, c0 = -1, c1 = -1, c2 = -1;
for (int i = 0;  i < n02;  i++) {
if (s[SA12[i]] != c0 || s[SA12[i]+1] != c1 || s[SA12[i]+2] != c2) {
name++;  c0 = s[SA12[i]];  c1 = s[SA12[i]+1];  c2 = s[SA12[i]+2];
}
if (SA12[i] % 3 == 1) { s12[SA12[i]/3]      = name; } // left half
else                  { s12[SA12[i]/3 + n0] = name; } // right half
}

// recurse if names are not yet unique
if (name < n02) {
suffixArray(s12, SA12, n02, name);
// store unique names in s12 using the suffix array
for (int i = 0;  i < n02;  i++) s12[SA12[i]] = i + 1;
} else // generate the suffix array of s12 directly
for (int i = 0;  i < n02;  i++) SA12[s12[i] - 1] = i;

// stably sort the mod 0 suffixes from SA12 by their first character
for (int i=0, j=0;  i < n02;  i++) if (SA12[i] < n0) s0[j++] = 3*SA12[i];

// merge sorted SA0 suffixes and sorted SA12 suffixes
for (int p=0,  t=n0-n1,  k=0;  k < n;  k++) {
#define GetI() (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2)
int i = GetI(); // pos of current offset 12 suffix
int j = SA0[p]; // pos of current offset 0  suffix
if (SA12[t] < n0 ?
leq(s[i],       s12[SA12[t] + n0], s[j],       s12[j/3]) :
leq(s[i],s[i+1],s12[SA12[t]-n0+1], s[j],s[j+1],s12[j/3+n0]))
{ // suffix from SA12 is smaller
SA[k] = i;  t++;
if (t == n02) { // done --- only SA0 suffixes left
for (k++;  p < n0;  p++, k++) SA[k] = SA0[p];
}
} else {
SA[k] = j;  p++;
if (p == n0)  { // done --- only SA12 suffixes left
for (k++;  t < n02;  t++, k++) SA[k] = GetI();
}
}
}
delete [] s12; delete [] SA12; delete [] SA0; delete [] s0;
}

#include "stdio.h"

#define maxn 5050
#define Rep(i,n) for(int i=0,lll=(n);i<lll;++i)
#define For(i,a,n) for(int i=(a),lll=(n);i<=lll;++i)
#define Ford(i,a,n) for(int i=(a),lll=(n);i>=lll;--i)

int a[maxn], n, SA[maxn], lcp[maxn];

void init_lcp() {
int *inv=new int[maxn];
int h=0;
Rep(i,n-1) inv[SA[i]]=i;
Rep(i,n-1) if(inv[i]>0) {
int j=SA[inv[i]-1];
while(a[i+h]==a[j+h]) ++h;
lcp[inv[i]]=h;
--h;
if(h<0) h=0;
}
}

bool testok(int len) {
for(int i=0;i<n-1;) {
int j=i+1, mm=100000, MM=-1;
while((j<n-1) && (lcp[j]>=len-1)) ++j;
For(k,i,j-1) {
if(mm>SA[k]) mm=SA[k];
if(MM<SA[k]) MM=SA[k];
}
if(MM-mm>=len) return true;
i=j;
}
return false;
}

int main() {
scanf("%d",&n);
Rep(i,n) scanf("%d",a+i);
Rep(i,n-1) a[i]=a[i+1]-a[i]+90;
a[n-1]=0;
suffixArray(a,SA,n-1,200);
init_lcp();
int L=4, R=n,mid;
for(;L<R;mid=(L+R)/2+1, testok(mid) ? (L=mid) : (R=mid-1));
if(L==4) printf("0\n");
else printf("%d\n",L);
return 0;
}