/* Class: COP3530
 * Date: Jan 13, 2006
 * Instructor: Arup Guha
 * TA: Adam Campbell
 *
 * Recitation #1, Problem #2
 **/

import java.io.*;
import java.util.StringTokenizer;

public class Rec1Prob2{

	/* I have main throw exception so I don't need the try/catch blocks everywhere when reading in from the file.
	 * In general, this is not good programming practice, but for these simple problems we are more interested in the
	 *   algorithm.
	 **/
	public static void main(String[] args) throws Exception{

		int[] array;
		int n; // the number of elements in the array
		int target;
		BufferedReader userInputReader, fileReader;
		String fileName;
		StringTokenizer tokenizer;

		// initialize the BufferedReader to read from standard input
		userInputReader = new BufferedReader(new InputStreamReader(System.in));

		// prompt the user for the file name, and get the file name from the user
		System.out.print("Please enter the file name: ");
		fileName = userInputReader.readLine();

		// open up the input file
		fileReader = new BufferedReader(new FileReader(fileName));

		// read n and initialize the array
		n = Integer.parseInt(fileReader.readLine());
		array = new int[n];

		// get the line with all of the array values
		tokenizer = new StringTokenizer(fileReader.readLine());

		for(int i = 0; i < n; i++){
			array[i] = Integer.parseInt(tokenizer.nextToken());
		}

		// read target
		target = Integer.parseInt(fileReader.readLine());

		// print out the output, and we're done!
		if(Rec1Prob2.ArrayContainsValues(array, target)){
			System.out.println("The sum was found! :)");
		}else{
			System.out.println("The sum was not found. :(");
		}

	}

	// Returns true if the target is the sum of two numbers from the array
	// This functions runs in O(n) time
	public static boolean ArrayContainsValues(int[] array, int target){

		int leftIndex, rightIndex;

		// set the indeces appropriately
		leftIndex = 0;
		rightIndex = array.length - 1;

		// The trick is to keep these left and right indeces moving each iteration
		// Because the array is sorted, we know that if the leftmost and the rightmost
		//   elements have a sum less than the target, then the leftmost element cannot
		//   be a term in the sum.  Likewise, if the sum is greater than the target,
		//   the rightmost index can be moved to the left.
		while(leftIndex < rightIndex){

			// we need a bigger value, so move the leftIndex
			if(array[leftIndex] + array[rightIndex] < target){

				leftIndex++;

			// we need a smaller value, so move the right index
			}else if(array[leftIndex] + array[rightIndex] > target){

				rightIndex--;

			// the target was found
			}else{

				return true;

			}
		}

		return false;

	}

}