(* tra04.h8.43-44.pohja.p SJ *)

program kantalukulajittelu;

const	max = 1000000;			(* alkioiden määrä *)
		maxvalue = 10000000;	(* suurin arvo *)
		radix = 10000;			(* kantaluku *)

type 	taulu = array[1..max] of integer;

		radtaulu = array[0..radix-1] of integer;

(* laskee taulukon t (n kpl) esiintymät taulukkoon r, ja
   vielä r:n 0-alkusumman *)
procedure laskesijainnit(var t : taulu; n : integer; var r : radtaulu; offs : integer);
begin
	(* nollataan sijoitustaulukko *)
	(* lasketaan esiintymät *)
		j := (t[i] div offs) mod radix;
		r[j] := r[j] + 1;
	(* lasketaan 0-alkusumma *)
	end;
end; (* laskesijainnit() *)


(* siirtää lahde:n alkiot kohde:een (n kpl) sijaintitaulukon r
   mukaan *)
procedure siirra(var lahde, kohde : taulu; n : integer; var r : radtaulu; offs : integer);
begin
end; (* siirra() *)


(* lajittelu, vuorotellaan taulukkoja t ja apu *)
procedure radixsort(var t : taulu; n : integer);
	var apu : taulu;
		rad : radtaulu;
		i, offs : integer;
begin
	
	offs := 1;
	
	while (offs < maxvalue) do begin
		offs := offs * radix;
	end; (* while *)

end; (* radixsort() *)


(* pääohjelma *)

var	t : taulu;
	i, ed : integer;
	s1, s2 : longint;
	ok : boolean;

begin

	ok := true;

	s1 := 0;
	for i := 1 to max do begin
		t[i] := (* i; *) random(maxvalue-1);
		s1 := s1 + t[i];
	end;

	radixsort(t, max);

	(* tarkastus *)
	s2 := t[1];
	ed := t[1];
	for i := 2 to max do begin
		if (ed > t[i]) then
			ok := false;
		s2 := s2 + t[i];
	end;

	ok := ok and (s1 = s2);

	writeln(ok);
	(* *)
end.