Nakon što su se fino najeli rafaelo kuglica, Mirko i Slavko su odlučili da pomoću testa utvrde koliko je moguće držati koncentraciju sa punim stomakom. Test se sastoji u tome da Mirko govori brojeve Slavku (izgovarajući svaki put jedan od 400 omiljenih brojeva), i u proizvoljnom momentu traži od njega da mu kaže koji je K-ti broj po veličini od svih brojeva koje je rekao do tada. Na vama je da pomognete Slavku u odgovaranju na zadata pitanja. Razlog zašto želite da pomognete Slavku nije bitan.

Ulaz:

(Ulazni podaci se nalaze u datoteci brojanje.in) U prvom redu ulazno datoteke nalazi se broj N ( 5 ≤ N ≤ 100.000). Svaki od narednih N redova ima jedan od dva formata:

• 1 a - označava da je Mirko izgovorio broj a ( 0 ≤ a ≤ 65535).
• 2 k - označava da je Mirko tražio od Slavka da mu kaže koji je k-ti broj po veličini (garantuje se da će k biti manje ili jednako trenutnom broju izgovorenih brojeva) Napomenimo još jednom da će broj različitih izgovorenih brojeva biti ne veći od 400 (pojedini brojevi se mogu ponavljati).

Izlaz:

(Izlazne podatke upisati u datoteku brojanje.out) Za svaki red iz ulazne datoteke koji je oblika '2 k', ispisati u nov red izlazne datoteke odgovor na Mirkovo pitanje. Postojaće bar jedan takav red.

Primer:

7
1 0
1 1
1 5
2 1
2 3
1 2
2 3

0
5
2

/*
 *
 *  Brojanje, okruzno 2008/09
 *
 *  Autor : Rajko Nenadov (rajkon@gmail.com)
 *
 */

#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;

struct List
{
  long broj;
  long pojavljivanje;

  List *next;
};

// glava liste u kojoj cuvamo izgovorene brojeve
List *glava;

long N;

/*
 *   ukoliko se 'broj' nalazi u list, polje 'pojavljivanje' elementa u kom se nalazi povecamo za 1;
 *  inace dodajemo novi element u listu, ali tako da lista ostane sortirana po 'broj' polju.
 */
void ubaci(long broj)
{
  if (glava == NULL)
  {
    glava = (List*)malloc(sizeof(List));
    glava->broj = broj;
    glava->pojavljivanje = 1;
    glava->next = NULL;
  }
  else
  {
    List *prev = NULL;
    List *itr = glava;

    while (itr != NULL && (itr->broj < broj))
    {
      prev = itr;
      itr = itr->next;
    }

    if (itr != NULL && (itr->broj == broj))
    {
      // broj postoji u listi
      itr->pojavljivanje++;
    }
    else
    {
      List *novi = (List*)malloc(sizeof(List));
      novi->broj = broj;
      novi->pojavljivanje = 1;

      if (prev == NULL)
      {
        // dodajemo na pocetak liste
        novi->next = glava;
        glava = novi;
      }
      else
      {
        prev->next = novi;
        novi->next = itr;
      }
    }
  }
}


long nadji(long k)
{
  List *itr = glava;
  while (itr->pojavljivanje < k)
  {
    k -= itr->pojavljivanje;
    itr = itr->next;
  }

  return itr->broj;
}


int main()
{
  long long l1 = clock();
  FILE *fin = fopen("brojanje.01.in", "r");
  FILE *fout = fopen("brojanjer.01.out", "w");

  glava = NULL;

  fscanf(fin, "%ld", &N);
  for (long i = 0; i < N; i++)
  {
    long a, b;
    fscanf(fin, "%d %ld", &a, &b);

    if (a == 1)
      ubaci(b);
    else
      fprintf(fout, "%ld\n", nadji(b));
  }

  fclose(fin);
  fclose(fout);
  cout << clock() - l1 << endl;
  system("pause");
  return 0;
}