input
The first line of the input file contains an integer number N — the number of pairs you should build cartesian tree out of (1 ≤ N ≤ 50 000). The following N lines contain two numbers each — given pairs (ki, ai). For each pair |ki|, |ai| ≤ 30 000. All main keys and all auxiliary keys are different, i.e. ki ≠ kj and ai ≠ aj for each i ≠ j.