program SkipList;

type
  NodePtr = ^Node;
  Node = record
    data: Integer;
    next: array of NodePtr;
  end;

var
  head: NodePtr;

procedure initSkipList;
begin
  New(head);
  head^.data := -1;
  SetLength(head^.next, 1);
  head^.next[0] := nil;
end;

function randomLevel: Integer;
var
  level: Integer;
begin
  level := 1;
  while Random(2) = 0 do
    level := level + 1;
  randomLevel := level;
end;

procedure insertElement(data: Integer);
var
  update: array of NodePtr;
  current: NodePtr;
  newLevel, i: Integer;
begin
  New(current);
  current^.data := data;
  
  newLevel := randomLevel;
  SetLength(current^.next, newLevel);
  SetLength(update, newLevel);
  
  for i := 0 to newLevel - 1 do
    update[i] := head;
  
  current := head;
  for i := newLevel - 1 downto 0 do
  begin
    while (current^.next[i] <> nil) and (current^.next[i]^.data < data) do
      current := current^.next[i];
    update[i] := current;
  end;
  
  for i := 0 to newLevel - 1 do
  begin
    current^.next[i] := update[i]^.next[i];
    update[i]^.next[i] := current;
  end;
end;

function searchElement(data: Integer): Boolean;
var
  current: NodePtr;
  i: Integer;
begin
  current := head;
  for i := Length(head^.next) - 1 downto 0 do
  begin
    while (current^.next[i] <> nil) and (current^.next[i]^.data < data) do
      current := current^.next[i];
  end;
  
  searchElement := (current^.next[0] <> nil) and (current^.next[0]^.data = data);
end;

procedure deleteElement(data: Integer);
var
  update: array of NodePtr;
  current: NodePtr;
  i: Integer;
begin
  current := head;
  for i := Length(head^.next) - 1 downto 0 do
  begin
    while (current^.next[i] <> nil) and (current^.next[i]^.data < data) do
      current := current^.next[i];
    update[i] := current;
  end;
  
  current := current^.next[0];
  if (current <> nil) and (current^.data = data) then
  begin
    for i := 0 to Length(current^.next) - 1 do
      update[i]^.next[i] := current^.next[i];
    Dispose(current);
  end;
end;

procedure printSkipList;
var
  current: NodePtr;
begin
  current := head^.next[0];
  while current <> nil do
  begin
    Write(current^.data, ' ');
    current := current^.next[0];
  end;
  Writeln;
end;

begin
  Randomize;
  initSkipList;
  
  insertElement(5);
  insertElement(10);
  insertElement(3);
  insertElement(8);
  
  printSkipList;
  
  if searchElement(3) then
    Writeln('Element 3 found')
  else
    Writeln('Element 3 not found');
  
  deleteElement(10);
  
  printSkipList;
end.