Search for a pair with a given sum in a sorted array

TypeScript Medium arrays

Task «Search for a pair with a given sum in a sorted array»

Given a sorted array of integers in ascending order and a target sum, it is necessary to find two distinct elements of the array whose sum equals the target sum. If there are several such elements, return the pair with the smallest indices (the first found from the left). If no pair is found, return an empty array. It is guaranteed that the array contains at least two elements.

Input Format

The first line contains an integer n — the number of elements in the array. The second line contains n integers separated by spaces. The third line contains an integer target — the target sum.

Output Format

Two numbers separated by a space, or an empty string if no pair is found.

Examples

Example 1

INPUT

4
-3 0 1 4
1

OUTPUT

-3 4

Example 2

INPUT

3
1 1 1

OUTPUT

1 1

Example 3

INPUT

3
10 20 30
15

OUTPUT

main.ts