583. Find Corresponding Index

0

Easy

Given an array of integers, find two numbers that add up to a specific target number. The function `twoSum` should return the indices of the two numbers such that they add up to the target, where `index1 < index2`. The returned indices should not be zero-based. The numbers should be put in order in an array and returned from the function. If no pair exists, return -1. If multiple solutions exist, output the one where `index2` is the minimum. If there are multiple solutions with the minimum `index2`, choose the one with the minimum `index1` out of them.

Input Format

The first line of the input contains an integer n, denoting the size of the array. The next n inputs are the values of the array. The next line contains an integer input for the target.

Output Format

Return an empty list if no solution exists. Return an array containing the indices (non-zero based) of the two numbers that add up to the target.

Example

Input

4 2 7 11 15 9

Output

1 2

Constraints

2 <= arr.length <= 10^4 -10^9 <= arr[i] <= 10^9 -10^9 <= target <= 10^9