Two Sum

⚡ Difficulty: Easy 🏷️ Topic: Arrays + Hashing

Given an array of integers and a target, return the indices of the two numbers that add up to the target.

Input

• Line 1: integer n — the size of the array.
• Line 2: n space-separated integers.
• Line 3: the integer target.

Exactly one valid answer exists, and you may not use the same element twice.

Output

• The two 0-based indices i j (with i < j) separated by a single space.

Example

Input:
4
2 7 11 15
9

Output:
0 1

Because nums[0] + nums[1] == 2 + 7 == 9.

Want the full explanation and optimal approach? Read the Two Sum II solution walkthrough or browse all problems.