Two Sum Problem

Given an array of integers and a target integer, your task is to find two distinct indices i and j (with i < j) such that:

$$A[i] + A[j] = T$$

If such a pair exists, output the indices separated by a space; otherwise, output -1.

Note that the array may contain negative numbers and duplicate values. The solution should work in O(n) expected time using appropriate data structures.

inputFormat

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

1. The first line contains a single integer n, representing the number of elements in the array.
2. The second line contains n space-separated integers denoting the array elements.
3. The third line contains a single integer, the target sum T.

outputFormat

Output the 0-indexed positions of the two numbers that add up to the target, separated by a space. If no such pair exists, output -1. The output should be printed to standard output (stdout).## sample

4
2 7 11 15
9

0 1