20127번 - Y-수열

N개의 정수로 이루어진 수열 a₁, ... , a_N이 있다. 택희는 해당 수열이 증가수열 혹은 감소수열이 되게 만들고 싶다.

증가수열은 모든 i(1 ≤ i < N)에 대해서 a_i ≤ a_i+1을 만족하는 수열이고, 감소수열은 a_i ≥ a_i+1을 만족하는 수열이다.

택희는 해당 수열의 맨 앞의 k개의 원소를 맨 뒤로 옮겨서 증가수열 또는 감소수열을 만들고 싶다. 즉, a_k+1, ..., a_N, a₁, ..., a_k가 증가수열, 또는 감소수열이 돼야 한다. 옮기지 않는 경우는 k=0이라고 하자. 이때, 적절한 k를 골라서 원하는 수열을 만들 수 있게 도와줘라.

다음과 같이 입력이 주어진다.

증가수열, 또는 감소수열을 만들 수 있는 k를 출력하여라. 가능한 k가 여러 개면 가능한 가장 작은 k를 출력하여라. 만약에 그런 k가 존재하지 않는다면 -1을 출력하여라.

• 1 ≤ N ≤ 1,000,000.
• 1 ≤ a_i ≤ 1,000,000,000. (1 ≤ i ≤ N)
• 입력에 주어진 수들은 전부 정수다.