Challenge: First and Last Position

Lab C++ Intermediate 20 points

Read a sorted list (values may repeat) and a target. Print the first and last index of the target, or -1 -1. Use lower_bound and upper_bound.

Input

Line 1: n target. Line 2: n sorted numbers.

Output

first last

Example

Input

6 8
5 7 7 8 8 10

Output

3 4

Sample input available Sample output available

Editor

C++

Hints

lower_bound gives the first position ≥ target.

upper_bound gives the first position > target; the last copy is one before it.

Solution explanation

If both bounds are equal, the target isn't there.

Show solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    int first = lower_bound(v.begin(), v.end(), t) - v.begin();
    int after = upper_bound(v.begin(), v.end(), t) - v.begin();
    if (first == after) cout << "-1 -1" << endl;
    else cout << first << " " << after - 1 << endl;
    return 0;
}

Output

Answer