Search in Rotated Sorted Array With Duplicates

Search in Rotated Sorted Array With Duplicates

Determine whether a target exists in a rotated sorted array that may contain duplicates.

Input format

The first line contains N and the target. The second line contains N integers — a sorted array (duplicates allowed) rotated at some pivot.

Output format

Print true if the target exists in the array, otherwise false.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

7 0
2 5 6 0 0 1 2

true

7 3
2 5 6 0 0 1 2

false