import java.io.*;

public class ArrayTools {

// sequentialSearch(): examine unsorted list for a key 	
public static int sequentialSearch(int[] data, int key) {	
	for (int i = 0; i < data.length; ++i) {	
		if (data[i] == key) {	
			return i;	
			}	
	}	
	
	return -1;	
}	


// binarySearch(): examine sorted list for a key 	
public static int binarySearch(char[] data, char key) {	
	int left = 0;	
	int right = data.length - 1;	
	while (left <= right) {	
		int mid = (left + right)/2;	
		if (data[mid] == key) {	
			return mid;	
		}	
		else if (data[mid] < key) {	
			left = mid + 1;	
		}	
		else {	
			right = mid - 1;	
		}	
	}	
	
	return -1;	
}	


// class constant 	
private static final int MAX_LIST_SIZE = 1000;	
	
// valueOf(): produces a string representation	
public static void putList(int[] data) {	
	for (int i = 0; i < data.length; ++i) {	
		System.out.println(data[i]);	
	}	
}	
// getList(): extract up to MAX_LIST_SIZE values and returns them	
public static int[] getList() throws IOException {	
	BufferedReader stdin = new BufferedReader(	
			new InputStreamReader(System.in));	
	
	int[] buffer = new int[MAX_LIST_SIZE];	
	
	int listSize = 0;	
	
	for (int i = 0; i < MAX_LIST_SIZE; ++i) {	
		String currentInput = stdin.readLine();	
		if (!currentInput.equals("s")) {	
			int number = Integer.parseInt(currentInput);	
			buffer[i] = number;	
			++listSize;	
		}	
		else {	
			break;	
		}	
	}	
	
	int[] data = new int[listSize];	
	for (int i = 0; i < listSize; ++i) {	
		data[i] = buffer[i];	
	}	
	
	return data;	
}	
	
// reverse(): reverses the order of the element values 	
public static void reverse(int[] list) {	
	int n = list.length;	
	
	for (int i = 0; i < n/2; ++i) {	
		// swap element from front of list with corresponding element	
		// from the end of the list	
		int rmbr = list[i];	
		list[i] = list[n-1-i];	
		list[n-1-i] = rmbr;	
	}	
}	


// doubleCapacity(): create a duplicate list with extra capacity 
public static String[] doubleCapacity(String[] currList) {
	int n = currList.length;
	String[] biggerList = new String[2*n]; // get a bigger list

	for (int i = 0; i < n; ++i) {
	    biggerList[i] = currList[i];      // copy existing values
	}

	return biggerList;
}

// selectionSort(): sorts the elements of a 
public static void selectionSort(char[] v) {
	for (int i = 0; i < v.length-1; ++i) {
	// guess the location of the ith smallest element
		int guess = i;
		for (int j = i+1; j < v.length; ++j) {
			if (v[j] < v[guess]) { // is guess ok?
			// update guess to index of smaller element
				guess = j;
			}
		}

	// guess is now correct, so swap elements
		char rmbr = v[i];
		v[i] = v[guess];
		v[guess] = rmbr;
	}
}

}