Y-sequence

Interview

Time limit1sMemory limit1024 MB

Summary

Find the smallest k such that rotating the first k elements to the end makes the sequence non-decreasing or non-increasing, or report -1.

Level: Medium5 of 10
Topics: Array, Implementation, Greedy, Two pointers
Solved: No attempts yet

Problem

There is a sequence a1, ..., aN of N integers. Taekhee wants to turn it into an increasing sequence or a decreasing sequence.

An increasing sequence satisfies ai ≤ ai+1 for every i (1 ≤ i < N), and a decreasing sequence satisfies ai ≥ ai+1.

Taekhee wants to move the first k elements to the back to make the sequence increasing or decreasing. That is, ak+1, ..., aN, a1, ..., ak must be an increasing or a decreasing sequence. The case of moving nothing is k=0. Help Taekhee choose a suitable k to obtain the desired sequence.

Input

The input is given as follows.

N
a1 . . . aN

Output

Print a k that makes the sequence increasing or decreasing. If several such k exist, print the smallest one. If no such k exists, print -1.

Constraints

1 ≤ N ≤ 1,000,000.
1 ≤ ai ≤ 1,000,000,000. (1 ≤ i ≤ N)
Every number in the input is an integer.

Examples2

Example 1
Input
```
5
3 4 5 1 2
```
Expected output
```
3
```
Example 2
Input
```
5
3 5 4 1 2
```
Expected output
```
-1
```