Lower Bound and Upper Bound

Implement pair<int,int> count_and_index(const vector<int>& a, int x) (returns a (count, index) tuple in Python, a 2-element array in JavaScript) where a is sorted in non-decreasing order (it may contain duplicates; vector<int> in C++, list of ints in Python, array of numbers in JavaScript). Using lower_bound and upper_bound (Python: bisect_left and bisect_right from the bisect module; JavaScript has no bisect equivalent, so both bounds are hand-written), return a pair (count, index): count is the number of elements of a equal to x (i.e. upper_bound(x) - lower_bound(x)), and index is the position where x would first be inserted to keep a sorted (i.e. lower_bound(x) - a.begin()), which equals a.size() if x is greater than every element.

Example: count_and_index({1, 2, 2, 2, 5}, 2) returns {3, 1}: three 2s sit at indices 1..3, so lower_bound lands on index 1 and upper_bound on index 4, giving count = 4 - 1 = 3 and index = 1. count_and_index({1, 2, 2, 2, 5}, 3) returns {0, 4}: there's no 3, but both bounds agree it would be inserted at index 4, right before the 5.

Input format: each test in tests/*.in is laid out as:

• Line 1: n, the array length.
• Line 2: the n sorted values, space-separated.
• Next line: q, the number of queries.
• Next q lines: one integer x per line, a count_and_index(a, x) query.

Test 02.in reads:

1
10
3
10
5
15

This is a one-element array {10} with three queries: 10 (present), 5 (below every value), and 15 (above every value).

Where you'll use it:

• 34. Find First and Last Position of Element in Sorted Array
• 35. Search Insert Position