Two Sum II (Sorted)

Practice this coding question on Coding Gurukul.

Problem statement

A sorted list of measurements contains exactly one pair whose sum equals a target. Find the positions of those two entries using constant extra space. The positions are one-based and must be printed in increasing order. You must use two different entries, even when their values are equal.

Input format

First line: n target. Second line: n integers in nondecreasing order.

Output format

Print the two one-based positions, smaller first.

Constraints

2 <= n <= 100000; -1000000000 <= values, target <= 1000000000; exactly one valid index pair exists.

Sample input

4 9
2 7 11 15

Sample output

1 2