Two Sum Indices Finder

You are given an array of n integers and a target integer T. Your task is to find two distinct indices i and j such that:

\(a_i + a_j = T, \quad 1 \le i < j \le n\)

The indices are 1-based, and if there are multiple solutions, return the pair with the smallest first index, and if there is still a tie, the smallest second index. If no valid pair exists, output No valid pair.

This problem can be solved efficiently using a hash map to achieve an average time complexity of \(O(n)\).

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

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

outputFormat

If there exists a pair of indices \(i\) and \(j\) such that \(a_i + a_j = T\) (with \(1 \le i < j \le n\)), output the two indices in ascending order separated by a space. If no such pair exists, output No valid pair.

Output should be written to standard output (stdout).

5
2 7 11 15 1
9

1 2