아름다운 산맥

어떤 배열의 부분배열은 배열의 연속한 일부분이다. 배열을 부분배열로 분할한다는 것은 배열 전체를 겹치지 않게 덮는 부분배열들의 모음이다. 즉 배열의 각 원소가 정확히 하나의 부분배열에 속한다. 예를 들어 A = [3, 1, 4, 1, 5]일 때 [3, 1, 4]와 [1, 5]는 A를 부분배열로 분할한 것이지만, [3, 4, 5]는 A의 부분배열이 아니다.

여기까지는 어디서든 볼 수 있는 표준적인 정의다. 그런데 여기서 새로운 정의가 몇 가지 더 나온다.

정수 배열 A가 주어질 때, A의 부분배열 [Ai, Ai+1, . . . , Aj]가 산이란 i < k < j인 어떤 인덱스 k가 존재하여 Ai부터 Ak까지의 부분배열이 비감소하고 Ak부터 Aj까지의 부분배열이 비증가하는 경우를 말한다. 쉽게 말해 부분배열의 값들이 인덱스 k까지 “올라가다가” 그 뒤로 “내려가며”, 산의 모양을 닮는다는 뜻이다. 원소가 세 개 미만인 부분배열은 산이 될 수 없다.

정수 배열이 아름다운 산맥이란 산들로 분할할 수 있으면서, 마지막 산만 원소 개수가 더 적을 수 있고 나머지 산들은 모두 원소 개수가 같은 경우를 말한다.

예를 들어 [5, 10, 4, 1, 3, 2]는 아름다운 산맥이다. [5, 10, 4]와 [1, 3, 2]로 분할할 수 있고, 둘 다 산이면서 원소 개수가 같기 때문이다. 또 다른 예로 배열 [5, 10, 4, 4, 10, 20, 30, 20, 2, 3, 1]도 아름다운 산맥인데, [5, 10, 4, 4], [10, 20, 30, 20], [2, 3, 1]로 분할할 수 있기 때문이다.

양의 정수로 이루어진 배열이 주어지는데, 그중 일부 값이 비어 있을 수 있다. 양의 정수로 배열을 채워서 아름다운 산맥이 되게 만들 수 있는지 판별하라.

첫째 줄에는 배열의 원소 개수를 나타내는 정수 N (3 ≤ N ≤ 105)이 주어진다. 둘째 줄에는 N개의 정수 A1, A2, . . . , AN (Ai = −1 또는 1 ≤ Ai ≤ 109, i = 1, 2, . . . , N)이 주어지는데, Ai = −1은 배열의 i번째 원소를 정해야 함을 나타내고, 양수 값은 배열의 i번째 원소의 실제 값이다.

양의 정수로 배열을 채워서 아름다운 산맥이 되게 만들 수 있으면 대문자 “Y”를, 그렇지 않으면 대문자 “N”을 한 줄에 출력한다.