Search in Rotated Array with Duplicates and Return Range

HardArrayStringBinary SearchModified Binary SearchSearchRange Finding

You are given a sorted array that has been rotated at an unknown pivot and may contain duplicates. Given a target value, return the first and last position of that target in the array. If not found, return -1 -1.

This simulates searching in partially corrupted or shifted datasets.

Constraints

1 ≤ N ≤ 100000

Public Test Cases

Input:

4 5 6 7 0 1 2 2 2

Target: 2

Output:

6 8

Examples

Example 1

Input: [4, 5, 6, 7, 0, 1, 2, 2, 2], 2

Output: 6,8

Example 2

Input: [2, 2, 2, 3, 4, 2], 2

Output: 0, 5

Example 3

Input: [1, 1, 1, 1], 2

Output: -1, -1

Loading...

Input:

[4, 5, 6, 7, 0, 1, 2, 2, 2], 2

Expected Output:

6,8

Search in Rotated Array with Duplicates and Return Range

Constraints

Public Test Cases

Input:

Output:

Examples

Hint 1

Hint 2