## Editorial for Bán dừa

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

#include <iostream>
#include <algorithm>
#include <cstdio>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define N 1000100
using namespace std;

int re,n,a[N],m,st[N],pos[N];

int main()
{
int i;
cin >> n;
fr(i,1,n) scanf("%d",&a[i]);
st[0]=-1; m=pos[0]=0;
fr(i,1,n)
if (a[i]>st[m])
{
st[++m]=a[i]; pos[m]=i;
}
else
{
while (a[i]<=st[m])
{
re=max(re,(st[m]<=i-pos[m]+(a[i]==st[m])?st[m]:0));
m--;
}
st[++m]=a[i];
}
fr(i,1,m) re=max(re,(st[i]<=n-pos[i]+1?st[i]:0));
cout << re << endl;
return 0;
}


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

program kagain;
uses    math;
const   fi='';
fo='';
var     a:array[0..1000009] of longint;
left,right:array[0..1000009] of longint;
area,dau,cuoi,n,t,i,j:longint;
inp,oup:text;
procedure openFile;
begin
assign(inp,fi);
reset(inp);
assign(oup,fo);
rewrite(oup);
end;

procedure closeFile;
begin
close(inp);
close(oup);
end;

procedure process;
var     i,t:longint;
begin
area:=0;
for i:=1 to n do
begin
left[i]:=0;
right[i]:=0;
end;
left[1]:=0;
for i:=2 to n do
begin
t:=i-1;
while a[t]>=a[i] do
t:=left[t];
left[i]:=t;

end;

right[n]:=n+1;
for i:=n-1 downto 1 do
begin
t:=i+1;
while a[t]>=a[i] do
t:=right[t];
right[i]:=t;

end;

for i:=1 to n do
begin
t:=right[i]-left[i]-1;
if t>=a[i] then
area:=max(area,a[i]);
end;
end;

begin
openFile;
readln(inp,n);
for j:=1 to n do readln(inp,a[j]);
process;
write(oup,area);
close(oup);
end.


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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>
#include <sstream>
#include <iomanip>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
if(!*inp) { \
fread(BUF,1,BUFSIZE,stdin); \
inp=BUF; \
} \
INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
AM=0;\
GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
if (INP=='-') {AM=1;GETCHAR(INP);} \
j=INP-'0'; GETCHAR(INP); \
while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
if (AM) j=-j;\
}

int n, st[1000111], a[1000111], l[1000111], r[1000111], top;

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
GN(n); FOR(i,1,n) GN(a[i]);
top = 0; st[0] = 0;
FOR(i,1,n) {
while (top && a[st[top]] >= a[i]) top--;
l[i] = st[top] + 1;
st[++top] = i;
}
top = 0; st[0] = n+1;
FORD(i,n,1) {
while (top && a[st[top]] >= a[i]) top--;
r[i] = st[top] - 1;
st[++top] = i;
}
int res = 0, u;
FOR(i,1,n) {
u = r[i] - l[i] + 1;
if (u < a[i]) continue;
res = max(res, min(u, a[i]));
}
cout << res;
return 0;
}


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

#include <stdio.h>
#include <algorithm>
//#include <conio.h>
#define Max 1111111

using namespace std;

int T,n,k,a[Max],left[Max],right[Max],r[Max],l[Max];

int main()
{
scanf("%d",&n);
for(int j=1;j<=n;j++)
scanf("%d",&a[j]);
int u = 1;
r[1] = 1;
for(int i = 2;i<=n;i++){
if(a[i]<a[r[u]]){
while(a[i]<a[r[u]] && u>0){
right[r[u]] = i-1;
u--;
}
}
r[++u] = i;
if(i==n) for(int j = 1;j<=u;j++) right[r[j]] = n;
}

u = 1;
l[1] = n;
for(int i = n-1;i>0;i--){
if(a[i]<a[l[u]]){
while(a[i]<a[l[u]] && u>0){
left[l[u]] = i+1;
u--;
}
}
l[++u] = i;
if(i==1) for(int j = 1;j<=u;j++) left[l[j]] = 1;
}

//printf("%ld %ld %ld",left[4],left[3],left[2]);
int kq = 0;
for(int j=1;j<=n;j++)
{
if(a[j]<=right[j]-left[j]+1)
kq = max(kq,min(right[j]-left[j]+1,a[j]));
}
printf("%d",kq);
//getch();
}


## Comments

Please read the guidelines before commenting.

There are no comments at the moment.