## Editorial for Hàng cây

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

const fi='';
fo='';
maxn=100000;
var n,re,dem:longint;
a,b,d:array[1..maxn] of longint;

procedure rf;
var i:longint;
begin
assign(input,fi);
reset(input);
for i:=1 to n do
begin
b[i]:=i;
end;
close(input);
end;

procedure sort(l,r:longint);
var i,j,x,y,xx:longint;
begin
i:=l; j:=r; x:=a[(i+j) div 2]; xx:=b[(i+j) div 2];
repeat
while (a[i]<x) or ((a[i]=x) and (b[i]<xx)) do i:=i+1;
while (a[j]>x) or ((a[j]=x) and (b[j]>xx)) do j:=j-1;
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=b[i]; b[i]:=b[j]; b[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

function check(x:longint):boolean;
begin
check:=(x>0) and (x<=n);
end;

procedure pr;
var cur,i:longint;
begin
sort(1,n);
fillchar(d,sizeof(d),0);
dem:=0; re:=0; cur:=1;
repeat
inc(re);
while d[b[cur]]=1 do inc(cur);
d[b[cur]]:=1; inc(dem);
for i:=0 to 1 do
if check(b[cur]-1+2*i) and (d[b[cur]-1+2*i]=0) then
begin
inc(dem); d[b[cur]-1+2*i]:=1;
end;
inc(cur);
until dem=n;
end;

procedure wf;
begin
assign(output,fo);
rewrite(output);
write(re);
close(output);
end;

begin
rf;
pr;
wf;
end.


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

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 100005

bool dead[N]; int n;

int main() {
//freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
scanf( "%d", &n );
priority_queue< ii, vii, greater<ii> > qu;
fo(i,1,n) {
int t; scanf( "%d", &t );
qu.push(ii(t, i));
}
int res = 0;
for(; !qu.empty(); qu.pop()) {
int v = qu.top().se;
if( dead[v] == 0 ) {
++res;
}
}
printf( "%d\n", res );
return 0;
}


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

program firs;
uses    math;
const   fi='';
maxN=123456;
type    e=record
v,pos:longint;
end;
var     a:array[1..maxN] of e;
p:array[1..maxN] of longint;
check:array[1..maxN] of boolean;
n,res:longint;

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

procedure swap(i,j:longint);
var     t:e;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;

procedure sort(l,r:longint);
var     i,j:longint;
p:e;
begin
if l>=r then exit;
p:=a[random(r-l+1)+l];
i:=l;j:=r;
repeat
while (a[i].v<p.v) or ((a[i].v=p.v) and (a[i].pos<p.pos)) do inc(i);
while (a[j].v>p.v) or ((a[j].v=p.v) and (a[j].pos>p.pos)) do dec(j);
if i<=j then
begin
if i<j then swap(i,j);
inc(i);
dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;

procedure init;
var     i:longint;
begin
for i:=1 to n do
p[a[i].pos]:=i;
end;

procedure process;
var     i:longint;
begin
for i:=1 to n do
if not check[i] then
begin
inc(res);
check[i]:=true;
if a[i].pos>1 then
check[p[a[i].pos-1]]:=true;
if a[i].pos<n then
check[p[a[i].pos+1]]:=true;
end;
end;

begin
input;
sort(1,n);
init;
process;
write(res);
end.


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

//Written by RR
{$ifdef rr} {$r+,q+}
{$mode objfpc} {$inline off}
{$else} {$r-,q-}
{$mode objfpc} {$inline on}
{$endif} uses math; const FINP = ''; FOUT = ''; MAXN = 100111; snode = 262144; var f1,f2 : text; n,dead : longint; nn : array[1..snode] of longint; a : array[1..MAXN] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n); for i:=1 to n do read(f1,a[i]); end; procedure init(i,l,r:longint); inline; var mid,x,y:longint; begin if (l=r) then begin nn[i]:=l; exit; end; mid:=(l+r)>>1; init(i<<1,l,mid); init(i<<1+1,mid+1,r); x:=nn[i<<1]; y:=nn[i<<1+1]; if a[x]<=a[y] then nn[i]:=x else nn[i]:=y; end; procedure update(i,l,r,u:longint); inline; var mid,x,y:longint; begin if (l>r) then exit; if (u<l) or (r<u) then exit; if (u=l) and (r=u) then exit; mid:=(l+r)>>1; update(i<<1,l,mid,u); update(i<<1+1,mid+1,r,u); x:=nn[i<<1]; y:=nn[i<<1+1]; if a[x]<=a[y] then nn[i]:=x else nn[i]:=y; end; procedure solve; var time,u:longint; begin dead:=0; time:=0; while dead<n do begin inc(time); u:=nn[1]; if (u>1) and (a[u-1]<MAXN) then begin a[u-1]:=MAXN; update(1,1,n,u-1); inc(dead); end; if (a[u]<MAXN) then begin a[u]:=MAXN; update(1,1,n,u); inc(dead); end; if (u<n) and (a[u+1]<MAXN) then begin a[u+1]:=MAXN; update(1,1,n,u+1); inc(dead); end; end; writeln(f2,time); end; begin openF; inp; init(1,1,n); solve; closeF; end.  #### Code mẫu của hieult #include <stdio.h> //#include <conio.h> void Quicksort(long A[],long a[],long x,long y) { long t=A[(x+y)/2]; long i=x; long j=y; while(i<=j) { while(A[i]<t) i++; while(A[j]>t) j--; if(i<=j) { long tg=A[i]; A[i]=A[j]; A[j]=tg; long tga=a[i]; a[i]=a[j]; a[j]=tga; i++; j--; } } if(j>x) Quicksort(A,a,x,j); if(i<y) Quicksort(A,a,i,y); } main() { long n,A[100002],a[100002],Free[100002],u=1,v,dem=0; scanf("%ld",&n); for(long i=1;i<=n;i++) { scanf("%ld",&A[i]); a[i]=i; Free[i]=0; } A[n+1]=0; Quicksort(A,a,1,n); while(u!=n&&u!=n+1) { if(A[u]!=A[u+1]) u++; else { v=u+1; while(A[v]==A[v+1]) v++; Quicksort(a,Free,u,v); u=v+1; } } //printf("%ld %ld %ld ",n,a[1],Free[a[1]]); for(long i=1;i<=n;i++) if(Free[a[i]]==0) { Free[a[i]]=1; Free[a[i]-1]=1; Free[a[i]+1]=1; dem++; } printf("%ld",dem); //getch(); }  #### Code mẫu của ll931110 {$MODE DELPHI}
program FIRS;
uses math;
const
input  = '';
output = '';
maxn = 100000;
maxv = 10000000;
type
rec = record
val,pos: integer;
end;
var
a: array[1..maxn] of integer;
s: array[1..8 * maxn] of rec;
n,res,u,v: integer;

procedure init;
var
f: text;
i: integer;
begin
assign(f, input);
reset(f);

for i := 1 to n do read(f, a[i]);

close(f);

for i := 1 to 8 * maxn do s[i].val := maxv;
end;

procedure combine(i: integer);
begin
s[i].val := min(s[2 * i].val,s[2 * i + 1].val);
if s[2 * i + 1].val < s[2 * i].val then s[i].pos := s[2 * i + 1].pos
else s[i].pos := s[2 * i].pos;
end;

procedure build(i,low,high: integer);
var
mid: integer;
begin
if low > high then exit;
if low = high then
begin
s[i].val := a[low];
s[i].pos := low;
exit;
end;

mid := (low + high) div 2;
build(2 * i,low,mid);
build(2 * i + 1,mid + 1,high);
combine(i);
end;

procedure update(i,low,high: integer);
var
mid: integer;
begin
if (v < low) or (high < u) then exit;
if s[i].val = maxv then exit;

if (u <= low) and (high <= v) then
begin
s[i].val := maxv;
s[i].pos := 0;
exit;
end;

mid := (low + high) div 2;
update(2 * i,low,mid);
update(2 * i + 1,mid + 1,high);
combine(i);
end;

procedure solve;
var
t: integer;
begin
res := 0;
repeat
t := s[1].pos;
if t <> 0 then
begin
inc(res);
u := t - 1;
v := t + 1;

if t = 1 then u := 1
else if t = n then v := n;

update(1,1,n);
end;
until s[1].pos = 0;
end;

procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
writeln(f, res);
close(f);
end;

begin
init;
build(1,1,n);
solve;
printresult;
end.


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

#include<stdio.h>
#include<queue>
#define MAX   100100
using namespace std;
typedef pair<int,int> ii;
bool b[MAX];
int n,c;
priority_queue<ii,vector<ii>,greater<ii> > q;
void init(void) {
int i,x;
scanf("%d",&n);
for (i=1;i<=n;i=i+1) {
scanf("%d",&x);
q.push(ii(x,i));
b[i]=true;
}
}
void process(void) {
c=0;
ii x;
int i;
while (!q.empty()) {
while ((!q.empty()) && (!b[q.top().second])) q.pop();
if (!q.empty()) {
x=q.top();
q.pop();
c=c+1;
for (i=-1;i<=1;i=i+1) b[x.second+i]=false;
}
}
printf("%d",c);
}
int main(void) {
init();
process();
}


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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

using namespace std;

#define Rep(i,n) for(int i=0,lll=(n);i<lll;++i)
#define For(i,a,b) for(int i=(a),lll=(b);i<=lll;++i)
#define Ford(i,a,b) for(int i=(a),lll=(b);i>=lll;--i)
#define pb push_back
#define MP make_pair
#define fi first
#define se second
#define nextint __nextint()

inline int __nextint() { int x; scanf("%d", &x); return x; }

const int MAXN = 100010;

int n;
int a[MAXN];
int mm[MAXN * 4];
// bool mark[MAXN];

void init(int n, int l, int r) {
if(l==r) {
// cout << l << " " << a[l] << " day " << endl;
mm[n] = a[l];
return;
}
else {
int m = (l+r) / 2;
init(2 *n, l,m );
init(2*n+1,m+1,r);
mm[n] = min(mm[n*2], mm[n*2+1]);
}
}

int findmin(int n, int l, int r) {
// cout << "find min " << n << " " << l << " " << r << endl;
if(l==r) return l;
int m = (l+r) / 2;
if(mm[n] == mm[2*n]) return findmin(2*n,l,m);
else return findmin(2*n+1,m+1,r);
}

int getvalue(int n,int l, int r, int pos) {
if(l==r) return mm[n];
else {
int m = (l+r)  / 2;
if(pos <= m) return getvalue( 2 * n, l, m, pos);
else return getvalue( 2 * n + 1, m +1, r, pos);
}
}

void update(int n, int l, int r, int pos, int val) {
if(l==r) {
mm[n] = val;
return;
}
else {
int m = (l+r) / 2;
if(pos <= m) update( 2 * n, l, m, pos, val);
if(m < pos) update(2*n+1,m+1,r,pos,val);
mm[n] = min(mm[n*2], mm[n*2+1]);
}
}

int main() {
scanf("%d", &n);
Rep(i,n) scanf("%d", a+i);

init(1,0,n-1);

//cout << mm[1] << " " << mm[2] << " " << mm[3] << endl;

int ngay = 0;
while(true) {
int pos = findmin( 1, 0, n-1);
int value = getvalue( 1, 0, n-1, pos);
// printf("%d %d\n", pos, value);
if(value >= 1000000) break;
else {
++ngay;
update( 1, 0, n-1, pos, 1000000);
if(pos > 0) update( 1, 0, n-1, pos - 1, 1000000);
if(pos + 1 < n) update( 1, 0, n-1, pos + 1, 1000000);
}

}

printf("%d\n", ngay);

return 0;
}