FIRS - Hàng cây
Tác giả: ll931110
Ngôn ngữ: Pascal
{$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);
readln(f, n);
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.