// Sortowanie przez wstawianie ze stosami
// Data: 21.08.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------------

program Stackinsort;

type // typ elementów dla stosów
  Tinteger = array of integer;

var
  SL, SP   : Tinteger; // stosy
  SLp, SPp : integer;  // indeksy szczytów stosów
  n        : integer;  // liczba elementów wejściowych
  v        : integer;  // wartość elementu
  i        : integer;  // licznik

begin

  readln(n); // odczytujemy liczbę elementów

  SetLength(SL, n+2); // tworzymy stosy
  SetLength(SP, n+2);

  SLp := 1; SPp := 1; // inicjujemy stosy

  SL[0] := -MAXINT-1; // najmniejsza wartość
  SP[0] := MAXINT; // największa wartość

  for i := 1 to n do // przetwarzamy dane wejściowe
  begin
    read(v); // odczytujemy daną z wejścia

    while SL[SLp-1] > v do
    begin
      Dec(SLp);
      SP[SPp] := SL[SLp]; // przenosimy z SL do SP
      Inc(SPp); // wszystkie elementy większe od v
    end;

    while SP[SPp-1] < v do
    begin
      Dec(SPp);
      SL[SLp] := SP[SPp]; // przenosimy z SP do SL
      Inc(SLp); // wszystkie elementy mniejsze od v
    end;

    SL[SLp] := v; // v umieszczamy w SL
    Inc(SLp);
  end;

  readln;

  while SLp > 0 do // przenosimy stos SL do SP
  begin
    Dec(SLp);
    SP[SPp] := SL[SLp];
    Inc(SPp);
  end;

  dec(SPp); // usuwamy strażnika
  repeat
    dec (SPp); // przesyłamy SP na wyjście
    v := SP[SPp];
    if SPp > 0 then write(v, ' ');
  until SPp = 0;

  writeln;

  SetLength(SL, 0); // usuwamy stosy z pamięci
  SetLength(SP, 0);

end.

// Sortowanie przez wstawianie ze stosami
// Data: 21.08.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>

using namespace std;

int main()
{
  int * SL, * SP; // stosy
  int SLp = 0, SPp = 0; // indeksy szczytów stosów
  int n; // liczba elementów wejściowych
  int v; // wartość elementu

  cin >> n; // odczytujemy liczbę elementów

  SL = new int[n+2]; // tworzymy stosy
  SP = new int[n+2];

  SLp = SPp = 1; // inicjujemy stosy

  SL[0] = -2147483648; // najmniejsza wartość
  SP[0] =  2147483647; // największa wartość

  for(int i = 0; i < n; i++) // przetwarzamy dane wejściowe
  {
    cin >> v; // odczytujemy daną z wejścia

    while(SL[SLp-1] > v)
      SP[SPp++] = SL[--SLp]; // przenosimy z SL do SP wszystkie
                             // elementy większe od v
    while(SP[SPp-1] < v)
      SL[SLp++] = SP[--SPp]; // przenosimy z SP do SL wszystkie
                             // elementy mniejsze od v
    SL[SLp++] = v; // v umieszczamy w SL
  }

  while(SLp)
    SP[SPp++] = SL[--SLp]; // przenosimy stos SL do SP

  SPp--; // usuwamy strażnika

  do // przesyłamy SP na wyjście
  {
    v = SP[--SPp];
    if(SPp) cout << v << " ";
  } while(SPp);

  cout << endl;

  delete [] SL; // usuwamy stosy
  delete [] SP;

  return 0;
}

' Sortowanie przez wstawianie ze stosami
' Data: 21.08.2012
' (C)2020 mgr Jerzy Wałaszek
'---------------------------------------

Dim As Integer Ptr SL, SP ' stosy
Dim As integer SLp = 1, SPp = 1 ' indeksy szczytów stosów
Dim n As Integer ' liczba elementów wejściowych
Dim v As Integer ' wartość
Dim i As Integer ' licznik

Open Cons For Input As #1

Input #1, n ' odczytujemy liczbę elementów

SL = New Integer[n+2] ' tworzymy stosy
SP = New Integer[n+2]

SL[0] = -2147483648 ' najmniejsza wartość
SP[0] =  2147483647 ' największa wartość

for i = 1 To n ' przetwarzamy dane wejściowe

  Input #1, v ' odczytujemy daną z wejścia

  While SL[SLp-1] > v
    SLp -= 1
    SP[SPp] = SL[SLp] ' przenosimy z SL do SP wszystkie
    SPp += 1 ' elementy większe od v
  Wend
 
  While SP[SPp-1] < v
    SPp -= 1
    SL[SLp] = SP[SPp] ' przenosimy z SP do SL wszystkie
    SLp += 1 ' elementy mniejsze od v
  Wend
 
  SL[SLp] = v ' v umieszczamy w SL
  SLp += 1
 
Next

Close #1

While SLp > 0
  SLp -= 1
  SP[SPp] = SL[SLp] ' przenosimy stos SL do SP
  SPp += 1
Wend

SPp -= 1 ' usuwamy strażnika

Do ' przesyłamy SP na wyjście
  SPp -= 1
  v = SP[SPp]
  if SPp > 0 Then Print Using "& ";v;
loop While SPp > 0

Print

Delete [] SL ' usuwamy stosy
Delete [] SP

End

# Sortowanie przez wstawianie ze stosami
# Data: 17.06.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------------------

# indeksy szczytów stosów
sl_ptr = 1
sp_ptr = 1
# odczytujemy liczbę elementów
n = int(input())
# tworzymy stosy
sl = [0] * (n+2)
sp = [0] * (n+2)
# najmniejsza wartość
sl[0] = -2147483648
# największa wartość
sp[0] =  2147483647
arr = input().split()
# przetwarzamy dane wejściowe
for i in range(n):
    # odczytujemy daną z wejścia
    v = int(arr[i])
    while sl[sl_ptr-1] > v:
        sl_ptr -= 1
        # przenosimy z sl do sp wszystkie
        sp[sp_ptr] = sl[sl_ptr]
        # elementy większe od v
        sp_ptr += 1
    while sp[sp_ptr-1] < v:
        sp_ptr -= 1
        # przenosimy z sp do sl wszystkie
        sl[sl_ptr] = sp[sp_ptr]
        # elementy mniejsze od v
        sl_ptr += 1
    # v umieszczamy w sl
    sl[sl_ptr] = v
    sl_ptr += 1
while sl_ptr > 0:
    sl_ptr -= 1
    # przenosimy stos sl do sp
    sp[sp_ptr] = sl[sl_ptr]
    sp_ptr += 1

# usuwamy strażnika
sp_ptr -= 1
# przesyłamy sp na wyjście
while True:
    sp_ptr -= 1
    v = sp[sp_ptr]
    if sp_ptr:
        print(v, end=" ")
    if not sp_ptr: break
print()