Challenge: First and Last Position

Lab Python Intermediate 20 points

Read a sorted list (values may repeat) and a target. Print the first and last position of the target, or -1 -1 if it isn't there. Use binary search (two searches is fine).

Input

Line 1: sorted whole numbers. Line 2: the target.

Output

first last

Example

Input

5 7 7 8 8 10
8

Output

3 4

Sample input available Sample output available

Editor

Python

Hints

When you find the target, remember the index and keep searching.

For the first position keep going left; for the last, keep going right.

Solution explanation

Two binary searches: O(log n) each, even when the target repeats many times.

Show solution

def bound(a, t, first):
    lo, hi, ans = 0, len(a) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            ans = mid
            if first:
                hi = mid - 1
            else:
                lo = mid + 1
        elif a[mid] < t:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

a = list(map(int, input().split()))
t = int(input())
print(bound(a, t, True), bound(a, t, False))

Output

Answer