import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Whiteboard * * @author vanb */ public class whiteboard_vanb { public Scanner sc; public PrintStream ps; /** * A Max Segment Tree. * * @author vanb */ public class SegmentTree { /** The number of elements */ public int size; /** The tree itself */ public int tree[]; /** * Create a Segment Tree for a segment with 'size' elements. * * @param size Number of elements */ public SegmentTree( int size ) { this.size = size; // If there are n elements, then the number of leaves // in the Segment Tree could be up to k, where k is the smallest // power of 2 greater than or equal to n. int k = Integer.highestOneBit( size ); if( k!=size ) k<<=1; // A binary tree with k leaves will have k-1 internal nodes. // So, we need k+k-1 overall. But, we start at 1, not 0, so // we need one more, since there's one (at 0) we won't use. tree = new int[k + k]; // We're use -1 as a flag that a value hasn't been set here. Arrays.fill( tree, -1 ); } /** * Put a value over an interval into the Segment tree. * This is an internal method. * * @param node Index of the current node * @param lo Low index of the segment for this node * @param hi High index of the segment for this node * @param lower Lower bound of the interval of interest * @param upper Upper bound of the interval of interest * @param value Value to fill in the interval [lower,upper] */ private void put( int node, int lo, int hi, int lower, int upper, int value ) { if( lower<=lo && hi<=upper ) { tree[node] = value; } else { // Build left and right subtrees int mid = (hi+lo)/2; if( lower<=mid ) put( node+node, lo, mid, lower, upper, value ); if( upper>mid ) put( node+node+1, mid+1, hi, lower, upper, value ); } } /** * Put a value over an interval into the Segment tree. * This is an outward facing method. * * @param lower Lower bound of the interval of interest * @param upper Upper bound of the interval of interest * @param value Value to fill in the interval [lower,upper] */ public void put( int lower, int upper, int value ) { put( 1, 0, size-1, lower, upper, value ); } /** * Get a value from the Segment Tree. * This is an internal method. * * @param node Index of the current node * @param lo Low index of the segment for this node * @param hi High index of the segment for this node * @param index Index we want to get the value from * @return */ private int get( int node, int lo, int hi, int index ) { int result = -1; if( node0 ) highest = Math.min( highest, max-1 ); } } if( highest