#include <iostream>
#include <ctime>
#include <cmath>
#define NOT_IMPLEMENTED -70
using namespace std;

const int Max = 1000; // Maksymalna wartosc klucza drzewa

class BST
{

	// Struktura w�z�a drzewa.
	struct node
	{
		int less;
		int number;
		int key;	 // klucz wezla
		node *left;  // adres lewego potomka
		node *right; // adres prawego potomka
		node(int elem, node *l, node *r)
		{
			less = 0;
			number = 1;
			key = elem;
			left = l;
			right = r;
		}
	};

	//typedef node* tree;

private:
	void DestroyTree(node *&t) // Usuwanie poddrzewa o korzeniu t
	{
		if (t == NULL)
			return;
		DestroyTree(t->left);
		DestroyTree(t->right);
		delete t;
	}

	void Print(node *t) // Drukowanie poddrzewa o korzeniu t
	{
		if (t == NULL)
			return;
		Print(t->left);
		cout << t->key << " ";
		Print(t->right);
	}
	void PrintDetails(node *t)
	{
		if (t == NULL)
			return;
		cout << "Klucz: " << t->key << " " << endl;
		cout << "    LEWY SYN: ";
		if (t->left == NULL)
			cout << "PUSTE\n";
		else
			cout << t->left->key << " " << endl;
		cout << "    PRAWY SYN: ";
		if (t->right == NULL)
			cout << "PUSTE\n";
		else
			cout << t->right->key << " " << endl;
		PrintDetails(t->left);
		PrintDetails(t->right);
	}

public:
	node * root;					  // Korzen drzewa
	BST() { root = NULL; }		  // Konstruktor drzewa
	~BST() { DestroyTree(root); } // Destruktor drzewa

								  // Funkcja logiczna, zwraca TRUE, jesli klucz elem jest w drzewie, wpp zwraca FALSE
								  //
	bool Member(int elem)
	{
		node *t = root;
		while (t != NULL)
		{
			if (t->key == elem)
				return true; // Znaleziono wezel o kluczu elem
			if (elem > t->key)
				t = t->right;
			else
				t = t->left; // Schodzimy do odpowiedniego poddrzewa
		}
		return false; // Brak klucza elem w drzewie
	}

	// Procedura wstawiania elementu elem do drzewa
	//
	void Insert(int elem)
	{
		int q = 0;
		node *t = root;   // Aktualnie rozpatrywany wezel
		node *p = NULL;   // Ojciec aktualnie rozpatrywanego wezla
		while (t != NULL) // Dopoki istnieje wezel
		{
			if (elem == t->key) {
				t->number++;
				return;
			}
				 // Klucz elem jest juz w drzewie
			p = t;		// Aktualizuj ojca aktualnego w�z�a
			if (elem < t->key) {
				t->less++;
				t = t->left; // Schodzimy do lewego poddrzewa
			}
			else {
				q++;
				t = t->right; // Schodzimy do prawego poddrzewa
			}

		}
		t = new node(elem, NULL, NULL); // Utworzenie nowego w�z�a
		if (p == NULL)
			root = t; // Dotychczasowe drzewo bylo puste
		else		  // Dotychczasowe drzewo bylo niepuste
			if (elem < p->key)
				p->left = t;
			else
				p->right = t; // Dowiazanie nowego wezla do odpowiedniego poprzednika
		t->less == q;
	}

	//  BUDOWA DRZEWA
	//  O losowej liczbie wezlow
	//
	void BuildRandomTree()
	{
		int n = rand() % Max + 1;
		for (int i = 0; i < n; i++)
		{
			do
			{
				int elem = rand() % Max + 1;
				if (!Member(elem))
				{
					Insert(elem);
					break;
				}
			} while (true);
		}
	}

	// O n wezlach
	//
	void BuildTree(int n)
	{
		int m = 0;
		do
		{
			int elem = rand() % Max + 1;
			if (!Member(elem))
			{
				m++;
				Insert(elem);
			}
		} while (m < n);
	}

	//  DRUKOWANIE DRZEWA
	//
	// W porzadku Inorder
	void PrintTree()
	{
		Print(root);
		cout << endl;
	}

	// Szczegolowe
	void PrintDetailedTree()
	{
		PrintDetails(root);
	}

	//________________________________________________________________________
	// Uzupelnienie klasy zgodnie z zadaniem
	//________________________________________________________________________

	/// Funkcja zwraca różnicę pomiędzy przychodem uzyskanym z najbardziej dochodowej aukcji a najmniej dochodowej aukcji.
	/// Jeśli różnica nie jest możliwa do wyznaczenia - funkcja zwraca -1
	int AuctionDiff()
	{
		if (root == NULL) {
			return -1;
		}
		node* min = root;
		node* max = root;
		while (min->left != NULL) {
			min = min->left;
		}
		while (max->right != NULL) {
			max = max->right;
		}

		return max->key-min->key;
	}

	/// Funkcja zwraca liczbę aukcji, które uzyskały przychód równy p
	/// Jeśli aukcja o podanym przychodzie p nie istnieje - funkcja powinna zwrócić -1
	int HowManyAuctions(int p)
	{
		node* t = root;
		while (t != NULL) {
			if (t->key == p) {
				return t->number;
			}
			else if (t->key < p) {
				t = t->right;
			}
			else t = t->left;
		}


		return -1;
	}

	/// Funkcja zwraca liczbę aukcji, które uzyskały mniej niż a przychodu
	/// UWAGA: Zakładamy, że a nie jest większe niż najwyższy przychód z aukcji.
	/// Jeśli nie jest możliwe określenie ilości aukcji - funkcja powinna zwrócić -1
	int LowerThan(int a) {
		node* t = root;
		while (t != NULL) {
			if (t->key < a && t->right->key >= a) {
				return t->right->less;
			}
			else if (t->key < a &&  t->right->key < a) {
				t = t->right;
			}
			else if (t->key > a && t->left->key > a) {
				t = t->left;
			}
			else if (t->key >= a && t->left->key < a) {
				return t->less;
			}
			else if (t -> key == a)
				return t->less;

		}
		return -1;
	}

	//________________________________________________________________________
	// I to juz koniec definicji klasy BST :-)
	//________________________________________________________________________
};