#include <stdio.h>
enum {
	the_size = 100010
};
class FIBO_TREE {
	private : 
		struct TREE {
			int lid, rid, pid;
			int key;
			int cnt;
		} tree[the_size];
		int ROOT, tot;
		int stk[the_size], top;
		#define lid(id) tree[id].lid
		#define rid(id) tree[id].rid
		#define pid(id) tree[id].pid
		void ph(int id) {
			if(top == 3) {
				if(rid(stk[top-1]) == stk[top]&&rid(stk[top-2]) == stk[top-1]) {
					if(!lid(stk[top-2])&&!lid(stk[top-1])) {
						lid(stk[top-1]) = stk[top-2];
						stk[top-2] = stk[top-1];
						stk[top-1] = stk[top];
						top--;
					}
				} else if(lid(stk[top-1]) == stk[top]&&lid(stk[top-2]) == stk[top-1]) {
					if(!rid(stk[top-2])&&!rid(stk[top-1])) {
						rid(stk[top-1]) = stk[top-2];
						stk[top-2] = stk[top-1];
						stk[top-1] = stk[top];
						top--;
					}
				}
			}
			if(top > 3) {
				if(rid(stk[top-1]) == stk[top]&&rid(stk[top-2]) == stk[top-1]) {
					if(!lid(stk[top-2])&&!lid(stk[top-1])) {
						if(stk[top-2] == lid(stk[top-3])) 
							lid(stk[top-3]) = stk[top-1];
						else 
							rid(stk[top-3]) = stk[top-1];
						lid(stk[top-1]) = stk[top-2];
						stk[top-2] = stk[top-1];
						stk[top-1] = stk[top];
						top--;
					}
				} else if(lid(stk[top-1]) == stk[top]&&lid(stk[top-2]) == stk[top-1]) {
					if(!rid(stk[top-2])&&!rid(stk[top-1])) {
						if(stk[top-2] == lid(stk[top-3])) 
							lid(stk[top-3]) = stk[top-1];
						else 
							rid(stk[top-3]) = stk[top-1];
						rid(stk[top-1]) = stk[top-2];
						stk[top-2] = stk[top-1];
						stk[top-1] = stk[top];
						top--;
					}
				}
			}
			if(top == 4) {
				if(lid(stk[top-3]) == stk[top-2]&&rid(stk[top-2]) == stk[top-1]&&lid(stk[top-1]) == stk[top]) {
					if(!rid(stk[top-1])) {
						lid(stk[top-1]) = stk[top-2];
						rid(stk[top-1]) = stk[top-3];
						rid(stk[top-2]) = stk[top];
						lid(stk[top-3]) = 0;
						stk[top-3] = stk[top-1];
						stk[top-1] = stk[top];
						top--;
					}
				} else if(rid(stk[top-3]) == stk[top-2]&&lid(stk[top-2]) == stk[top-1]&&rid(stk[top-1]) == stk[top]) {
					if(!lid(stk[top-1])) {
						rid(stk[top-1]) = stk[top-2];
						lid(stk[top-1]) = stk[top-3];
						lid(stk[top-2]) = stk[top];
						rid(stk[top-3]) = 0;
						stk[top-3] = stk[top-1];
						stk[top-1] = stk[top];
						top--;
					}
				}
			}
			if(top > 4) {
				if(lid(stk[top-3]) == stk[top-2]&&rid(stk[top-2]) == stk[top-1]&&lid(stk[top-1]) == stk[top]) {
					if(!rid(stk[top-1])) {
						if(lid(stk[top-4]) == stk[top-3]) 
							
						lid(stk[top-1]) = stk[top-2];
						rid(stk[top-1]) = stk[top-3];
						rid(stk[top-2]) = stk[top];
						lid(stk[top-3]) = 0;
						stk[top-3] = stk[top-1];
						stk[top-1] = stk[top];
						top--;
					}
				} else if(rid(stk[top-3]) == stk[top-2]&&lid(stk[top-2]) == stk[top-1]&&rid(stk[top-1]) == stk[top]) {
					if(!lid(stk[top-1])) {
						rid(stk[top-1]) = stk[top-2];
						lid(stk[top-1]) = stk[top-3];
						lid(stk[top-2]) = stk[top];
						rid(stk[top-3]) = 0;
						stk[top-3] = stk[top-1];
						stk[top-1] = stk[top];
						top--;
					}
				}
			}
		}
};
signed main() {
	
}