// Wikipedia: https://en.wikipedia.org/wiki/AVL_tree
// This datastructure makes a slight modification to the AVL Tree.
// By keeping track of the number of nodes of the subtree rooted at each node,
// we can quickly find the index of a certain node by adding up all the counts
// left of that particular node, and vice versa.

// As is, it's pretty useless since it only stores the key and no data.
// That's cause I'm writing this for a silly programming puzzle, not for actual use.
class FastIndexTree {
	FastIndexTreeNode root;
}

class FastIndexTreeNode {
	FastIndexTreeNode *left;
	FastIndexTreeNode *right;
	int count;
	int key;
	int balance; // value in {-1, 0, 1}, see Wikipedia

	// Inserts a node and returns the change in height
	int insert(FastIndexTreeNode *node);
	// Removes a node and returns the change in height
	int remove(FastIndexTreeNode *node);
	// Finds the index of a particular value.
	int find(int key);
	// Finds the node containing a particular value.
	FastIndexTreeNode *search(int key);
	// Finds the node at a particular index.
	FastIndexTreeNode *at(int index);
}