#include <iostream>
using namespace std;
long long n;
long long count = 1;
bool found = false;
bool incr = false;
class BST
{
long long data, index;
BST *left, *right;
public:
// Default constructor.
BST();
// Parameterized constructor.
BST(long long, long long);
// Insert function.
BST* Insert(BST*, BST*, long long);
void Increment(BST*, long long);
// Inorder traversal.
void Inorder(BST*);
void IndexSearch(BST*, long long int);
};
BST ::BST()
: data(0)
, left(NULL)
, right(NULL)
, index(1)
{
}
BST ::BST(long long value, long long i)
{
data = value;
left = right = NULL;
index = i;
}
BST* BST ::Insert(BST* root, BST* parent, long long value)
{
if (!root)
{
if (parent && parent->data < value) {
return new BST(value, parent->index);
}
else if (parent && parent->data > value) {
return new BST(value, parent->index + 1);
}
else {
return new BST(value, 1);
}
}
if (value > root->data)
{
incr = true;
root->right = Insert(root->right, root, value);
}
else
{
root->left = Insert(root->left, root, value);
}
return root;
}
void BST ::Increment(BST* root, long long value) {
if (!root) {
return;
}
Increment(root->left, value);//, data);
if (root->data < value) root->index += 1;
if (root->right && root->right->data < value) {
Increment(root->right, value);//, data);
}
}
// Inorder traversal function.
// This gives data in sorted order.
void BST ::Inorder(BST* root)
{
if (!root) {
return;
}
Inorder(root->right);
cout << "index: " << root->index;
cout << " data: " << root->data << endl;
Inorder(root->left);
}
void BST ::IndexSearch(BST* root, long long value) {
if (!root) return;
else if (root->data == value) {
found = true;
cout << root->index << endl;
}
else if (root->data < value) IndexSearch(root->right, value);
else IndexSearch(root->left, value);
}
// Driver code
int main()
{
long long type, data;
BST b, *root = NULL;
cin >> n;
while (n--) {
cin >> type;
cin >> data;
if (!root) {
if (type == 1) root = b.Insert(root, NULL, data);
else if (type == 2) cout << "Data tidak ada\n";
}
else {
if (type == 1) {
b.Insert(root, NULL, data);
if (incr) b.Increment(root, data);
}
else {
b.IndexSearch(root, data);
if (!found) cout << "Data tidak ada\n";
}
}
incr = false;
found = false;
count = 1;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbG9uZyBsb25nIG47CmxvbmcgbG9uZyBjb3VudCA9IDE7CmJvb2wgZm91bmQgPSBmYWxzZTsKYm9vbCBpbmNyID0gZmFsc2U7CiAKY2xhc3MgQlNUCnsKICAgIGxvbmcgbG9uZyBkYXRhLCBpbmRleDsKICAgIEJTVCAqbGVmdCwgKnJpZ2h0OwogCnB1YmxpYzoKICAgIC8vIERlZmF1bHQgY29uc3RydWN0b3IuCiAgICBCU1QoKTsKIAogICAgLy8gUGFyYW1ldGVyaXplZCBjb25zdHJ1Y3Rvci4KICAgIEJTVChsb25nIGxvbmcsIGxvbmcgbG9uZyk7CiAKICAgIC8vIEluc2VydCBmdW5jdGlvbi4KICAgIEJTVCogSW5zZXJ0KEJTVCosIEJTVCosIGxvbmcgbG9uZyk7CiAKCXZvaWQgSW5jcmVtZW50KEJTVCosIGxvbmcgbG9uZyk7CgkKICAgIC8vIElub3JkZXIgdHJhdmVyc2FsLgogICAgdm9pZCBJbm9yZGVyKEJTVCopOwogICAgCiAgICB2b2lkIEluZGV4U2VhcmNoKEJTVCosIGxvbmcgbG9uZyBpbnQpOwp9OwogCgpCU1QgOjpCU1QoKQogICAgOiBkYXRhKDApCiAgICAsIGxlZnQoTlVMTCkKICAgICwgcmlnaHQoTlVMTCkKICAgICwgaW5kZXgoMSkKewp9CiAKQlNUIDo6QlNUKGxvbmcgbG9uZyB2YWx1ZSwgbG9uZyBsb25nIGkpCnsKICAgIGRhdGEgPSB2YWx1ZTsKICAgIGxlZnQgPSByaWdodCA9IE5VTEw7CiAgICBpbmRleCA9IGk7Cn0KIAoKQlNUKiBCU1QgOjpJbnNlcnQoQlNUKiByb290LCBCU1QqIHBhcmVudCwgbG9uZyBsb25nIHZhbHVlKQp7CiAgICBpZiAoIXJvb3QpCiAgICB7CiAgICAJaWYgKHBhcmVudCAmJiBwYXJlbnQtPmRhdGEgPCB2YWx1ZSkgewogICAgCQlyZXR1cm4gbmV3IEJTVCh2YWx1ZSwgcGFyZW50LT5pbmRleCk7CiAgICAJfQogICAgCWVsc2UgaWYgKHBhcmVudCAmJiBwYXJlbnQtPmRhdGEgPiB2YWx1ZSkgewogICAgCQlyZXR1cm4gbmV3IEJTVCh2YWx1ZSwgcGFyZW50LT5pbmRleCArIDEpOwogICAgCX0KICAgIAllbHNlIHsKICAgICAgICAJcmV0dXJuIG5ldyBCU1QodmFsdWUsIDEpOwogICAgCX0KICAgIH0KIAogICAgaWYgKHZhbHVlID4gcm9vdC0+ZGF0YSkKICAgIHsKICAgIAlpbmNyID0gdHJ1ZTsKICAgICAgICByb290LT5yaWdodCA9IEluc2VydChyb290LT5yaWdodCwgcm9vdCwgdmFsdWUpOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIHJvb3QtPmxlZnQgPSBJbnNlcnQocm9vdC0+bGVmdCwgcm9vdCwgdmFsdWUpOwogICAgfQogICAgCiAgICByZXR1cm4gcm9vdDsKfQogCnZvaWQgQlNUIDo6SW5jcmVtZW50KEJTVCogcm9vdCwgbG9uZyBsb25nIHZhbHVlKSB7CiAgICBpZiAoIXJvb3QpIHsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBJbmNyZW1lbnQocm9vdC0+bGVmdCwgdmFsdWUpOy8vLCBkYXRhKTsKICAgIGlmIChyb290LT5kYXRhIDwgdmFsdWUpIHJvb3QtPmluZGV4ICs9IDE7CiAgICBpZiAocm9vdC0+cmlnaHQgJiYgcm9vdC0+cmlnaHQtPmRhdGEgPCB2YWx1ZSkgewogICAgCUluY3JlbWVudChyb290LT5yaWdodCwgdmFsdWUpOy8vLCBkYXRhKTsKICAgIH0KfSAKIAovLyBJbm9yZGVyIHRyYXZlcnNhbCBmdW5jdGlvbi4KLy8gVGhpcyBnaXZlcyBkYXRhIGluIHNvcnRlZCBvcmRlci4Kdm9pZCBCU1QgOjpJbm9yZGVyKEJTVCogcm9vdCkKewogICAgaWYgKCFyb290KSB7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgSW5vcmRlcihyb290LT5yaWdodCk7CiAgICBjb3V0IDw8ICJpbmRleDogIiA8PCByb290LT5pbmRleDsKICAgIGNvdXQgPDwgIiBkYXRhOiAiIDw8IHJvb3QtPmRhdGEgPDwgZW5kbDsKICAgIElub3JkZXIocm9vdC0+bGVmdCk7Cn0KIAp2b2lkIEJTVCA6OkluZGV4U2VhcmNoKEJTVCogcm9vdCwgbG9uZyBsb25nIHZhbHVlKSB7CglpZiAoIXJvb3QpIHJldHVybjsKCWVsc2UgaWYgKHJvb3QtPmRhdGEgPT0gdmFsdWUpIHsKCQlmb3VuZCA9IHRydWU7CgkJY291dCA8PCByb290LT5pbmRleCA8PCBlbmRsOwoJfQoJZWxzZSBpZiAocm9vdC0+ZGF0YSA8IHZhbHVlKSBJbmRleFNlYXJjaChyb290LT5yaWdodCwgdmFsdWUpOwoJZWxzZSBJbmRleFNlYXJjaChyb290LT5sZWZ0LCB2YWx1ZSk7Cn0gCiAKLy8gRHJpdmVyIGNvZGUKaW50IG1haW4oKQp7Cglsb25nIGxvbmcgdHlwZSwgZGF0YTsKICAgIEJTVCBiLCAqcm9vdCA9IE5VTEw7CiAgICAKICAgIGNpbiA+PiBuOwogICAgCiAgICB3aGlsZSAobi0tKSB7CiAgICAJY2luID4+IHR5cGU7CiAgICAJY2luID4+IGRhdGE7CiAgICAJaWYgKCFyb290KSB7CiAgICAJCWlmICh0eXBlID09IDEpCQlyb290ID0gYi5JbnNlcnQocm9vdCwgTlVMTCwgZGF0YSk7CiAgICAJCWVsc2UgaWYgKHR5cGUgPT0gMikJY291dCA8PCAiRGF0YSB0aWRhayBhZGFcbiI7CiAgICAJfQogICAgCWVsc2UgewogICAgCQlpZiAodHlwZSA9PSAxKSB7CiAgICAJCQliLkluc2VydChyb290LCBOVUxMLCBkYXRhKTsKICAgIAkJCWlmIChpbmNyKSBiLkluY3JlbWVudChyb290LCBkYXRhKTsKICAgIAkJfQogICAgCQllbHNlIHsJCiAgICAJCQliLkluZGV4U2VhcmNoKHJvb3QsIGRhdGEpOwoJCQkJaWYgKCFmb3VuZCkgY291dCA8PCAiRGF0YSB0aWRhayBhZGFcbiI7CiAgICAJCX0KICAgIAl9CiAgICAJaW5jciA9IGZhbHNlOwogICAgCWZvdW5kID0gZmFsc2U7CiAgICAJY291bnQgPSAxOwogICAgfQoJcmV0dXJuIDA7Cn0KIA==