/*
 * $ java-algs4 PlainBSTStats 1000000 86
 * N = 1000000
 * Plain height = 49  (best possible = 19)
 * IPL = 24753714
 * Average depth = 24.7537  (best possible = 17.9514)
 * $ java-algs4 PlainBSTStats 10000000 86
 * N = 10000000
 * Plain height = 61  (best possible = 23)
 * IPL = 305805507
 * Average depth = 30.5806  (best possible = 21.3223)
 * $ 
 */

public class PlainBSTStats
{
    public static void main(String[] args)
    {
	int N = Integer.parseInt(args[0]);
	int[] a = RBBSTDraw.input(args);

	BSTDraw<Integer, Integer> st = new BSTDraw<>();

	for (int i = 0; i < N; i++)
	    st.put(a[i], i);
	
	StdOut.println("N = " + N);
	StdOut.printf("Plain height = %d  (best possible = %d)\n",
		      st.height(), RBBSTDraw.lgfloor(N)
		      );
	int ipl = st.iplP();
	StdOut.println("IPL = " + ipl);
	StdOut.printf("Average depth = %.4f  (best possible = %.4f)\n",
		      (double)ipl / N,
		      (double)RBBSTDraw.bestIPL(N) / N
		      );
    }
}