666. Find in Mountain Array

0

Hard

A mountain array, arr, is defined as an array with a length of at least 3, where there exists an index i (0 < i < arr.length - 1) such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]. Given a mountain array, Arr, find and print the minimum index, idx, such that Arr[idx] == target. If such an index does not exist, print -1.

Input Format

The first line contains two space-separated integers, N and target.
The second line contains an integer array, Arr, of size N.

Output Format

Print the minimum index.

Example

Input

7 3
1 2 3 4 5 3 1

Output

2

Constraints

3 <= N <= 10^5
0 <= nums[i] <= 10^9

Loading...

View Submissions

Console