public class TrickyInsert {

	public static void main(String[] args) {

		int[] mysteryArr = generateRandArr();
		
		//print out starting state of mysteryArr:
		System.out.print("start:\t");
		for ( int a : mysteryArr ) {
			System.out.print( a + ", ");
		}
		System.out.println();


		///////////////////////////////////
		// add your code after this line //
		///////////////////////////////////
		
		// insert value '8' in the appropriate place in mysteryArr[]
		


		

		
		///////////////////////////////////////
		// finish your code before this line //
		///////////////////////////////////////

		//print out ending state of mysteryArr:
		System.out.print("finish:\t");
		for ( int a : mysteryArr ) {
			System.out.print( a + ", ");
		}
		System.out.println();

	}

	
	private static int[] generateRandArr() {
		// this method returns an array that
		// * is of size 3, 4, 5, 6, 7, or 8
		// * contains only positive integers in ascending order
		// * may contain repeated elements
		
		// # elts may range from 3 to 8
		int numElts = 3 + (int)( Math.random() * 6 );
		int[] arr = new int[ numElts ];
		int[] tmp = new int[ numElts ];

		//populate tmp[] w/random pos ints
		for ( int i = 0 ; i < numElts ; i++ ) {
			tmp[i] = 1 + (int)(Math.random() * 100);
		}

		//for eights to occur more often for students
		//to see potential bug with multiple 8s 
		//in output array, have an 8 in the 
		//array 30% of the time:
		if ( Math.random() < .3 ) tmp[0] = 8;

		//go through tmp[] numElts times, grabbing
		//the greatest elt left and adding to arr[] in
		//reverse index order; will result in ascending
		//order in arr[]
		for ( int i = numElts - 1 ; i >= 0 ; i-- ) {
			//find greatest elt of tmp[]
			int max = 0, idxOfMax = 0;
			for ( int j = 0 ; j < numElts ; j++ ) {
				if ( tmp[j] > max ) {
					max = tmp[j];
					idxOfMax = j;
				}
			}
			arr[i] = max;
			tmp[idxOfMax] = 0; 
		}

		return arr;
	}

}