Y-수열
면접 대비시간 제한1초메모리 제한1024 MB
앞의 k개 원소를 뒤로 옮긴 수열이 비내림차순 또는 비오름차순이 되는 가장 작은 k를 구하고, 없으면 -1을 출력한다.
문제
N개의 정수로 이루어진 수열 a1, ..., aN이 있다. 택희는 이 수열을 증가수열 또는 감소수열로 만들려고 한다.
증가수열은 모든 i(1 ≤ i < N)에 대해 ai ≤ ai+1을 만족하는 수열이고, 감소수열은 ai ≥ ai+1을 만족하는 수열이다.
택희는 수열의 맨 앞 k개 원소를 맨 뒤로 옮겨서 증가수열 또는 감소수열을 만들려고 한다. 즉, ak+1, ..., aN, a1, ..., ak가 증가수열 또는 감소수열이어야 한다. 옮기지 않는 경우는 k=0이다. 적절한 k를 골라 택희가 원하는 수열을 만들 수 있도록 도와라.
입력
입력은 다음과 같이 주어진다.
N
a1 . . . aN
출력
증가수열 또는 감소수열을 만들 수 있는 k를 출력한다. 가능한 k가 여러 개면 가장 작은 k를 출력한다. 그런 k가 존재하지 않으면 -1을 출력한다.
제한
- 1 ≤ N ≤ 1,000,000.
- 1 ≤ ai ≤ 1,000,000,000. (1 ≤ i ≤ N)
- 입력에 주어진 수는 모두 정수다.