Two Sum

easy

100 pts · Time limit 2000 ms · Memory limit 256 MB · Leaderboard · arrays,hashing

You are given an array of integers and a target value. Print the 0-indexed positions of the two numbers that add up to the target, separated by a space. Assume exactly one valid pair exists.

Input Format

Line 1: an integer N, the size of the array. Line 2: N space-separated integers. Line 3: the target integer.

Output Format

Two space-separated integers: the indices of the two numbers, smaller index first.

Constraints

2 <= N <= 10^5 -10^9 <= array values, target <= 10^9

Sample 1

Input

4
2 7 11 15
9

Output

0 1

Sample 2

Input

3
3 2 4
6

Output

1 2

Discussion

No comments yet — ask a question or share a hint.