Two Sum Indices

Given an integer array A and a target integer T, find the 0-based indices of the two numbers such that they add up to T.

You may assume that each ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌‌​​‌‌​​​‌‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌​​​‌​‌‌​​​​‌​​‌‌​‌​​​​‌‌​​‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌​​​‌​​‌‌​​​​input has exactly one valid solution, and you may not use the same element twice. Print the two indices separated by a single space in ascending order.

---

Input Format

• Line 1: An integer N (2 ≤ N ≤ 100,000), the number of elements in the array.
• Line 2: N space-separated integers A[0], A[1], ..., A[N-1] (-10^9 ≤ A[i] ≤ 10^9). ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌‌​​‌‌​​​‌‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌​​​‌​‌‌​​​​‌​​‌‌​‌​​​​‌‌​​‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌​​​‌​​‌‌​​​​- Line 3: The target integer T (-2 × 10^9 ≤ T ≤ 2 × 10^9).

---

Output Format

• Print two space-separated integers representing the 0-based indices in ascending numerical order.

---

Example 1

Input:

4
2 7 11 15
9

Output:

0 1

Explanation: A[0] + A[1] = 2 + 7 = 9. Therefore, the indices are 0 1. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌‌​​‌‌​​​‌‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌​​​‌​‌‌​​​​‌​​‌‌​‌​​​​‌‌​​‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌​​​‌​​‌‌​​​​

Example 2

Input:

3
3 2 4
6

Output:

1 2

Explanation: A[1] + A[2] = 2 + 4 = 6. The indices are 1 2. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌‌​​‌‌​​​‌‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌​​​‌​‌‌​​​​‌​​‌‌​‌​​​​‌‌​​‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌​​​‌​​‌‌​​​​

3
3 2 4
6

1 2

4
2 7 11 15
9

0 1