Two Sum Existence

Given an array of integers and a target integer, determine whether there exist two distinct indices i and j in the array such that

\(a_i + a_j = target\)

The goal is to check if there is any pair of numbers in the array whose sum equals the target value. If such a pair exists, output 1; otherwise, output 0.

It is guaranteed that the array and target are provided in the input as described below.

inputFormat

The input is given via standard input (stdin) and consists of the following lines:

• The first line contains an integer n representing the number of elements in the array.
• The second line contains n space-separated integers representing the array elements.
• The third line contains an integer target representing the target sum.

For example:

4
1 2 3 9
8

outputFormat

Output a single integer to standard output (stdout):

• 1 if there exist two distinct indices i and j such that \(a_i + a_j = target\),
• 0 otherwise.

## sample

4
1 2 3 9
8

0