408545: GYM103185 B Beautiful Mountains

A subarray of an array is a contiguous portion of the array. A partition of an array into subarrays is a collection of subarrays that cover all the array without overlaps (each element in the array belongs to exactly one subarray). For instance, if $$$A=[3,1,4,1,5]$$$ is an array, $$$[3,1,4]$$$ and $$$[1,5]$$$ form a partition of $$$A$$$ into subarrays, while $$$[3,4,5]$$$ is not a subarray of $$$A$$$.

Those are standard definitions that you may have read elsewhere. So, what's new here? Well, a few more definitions follow. Given an array $$$A$$$ of integers, a subarray $$$[{A_i},{A_{i+1}}, \ldots, {A_j}]$$$ of $$$A$$$ is called a mountain if there exists an index $$$k$$$ such that $$$i < k < j$$$, the subarray from $$$A_i$$$ to $$$A_k$$$ is non-decreasing, and the subarray from $$$A_k$$$ to $$$A_j$$$ is non-increasing. In simple words, the values in the subarray "go up" until index $$$k$$$ and then "go down", resembling a mountain. Note that a subarray with fewer than three elements cannot be a mountain.

An array of integers is called a beautiful mountain chain if it can be partitioned into mountains, each of them having the same number of elements, except for the last mountain which may have fewer elements.

As an example, $$$[5,10,4,1,3,2]$$$ is a beautiful mountain chain because it can be partitioned into $$$[5,10,4]$$$ and $$$[1,3,2]$$$, being both mountains that have the same number of elements. Another example is the array $$$[5,10,4,4,10,20,30,20,2,3,1]$$$, which is also a beautiful mountain chain because it can be partitioned into $$$[5,10,4,4]$$$, $$$[10,20,30,20]$$$ and $$$[2,3,1]$$$.

Given an array of positive integers, where some values can be missing, determine if it is possible to complete the array with positive integers such that it becomes a beautiful mountain chain.

The first line contains an integer $$$N$$$ ($$$3 \leq N \leq 10^5$$$) indicating the number of elements in the array. The second line contains $$$N$$$ integers $$${A_1}, {A_2}, \ldots, {A_N}$$$ ($$$A_i=-1$$$ or $$$1 \leq A_i \leq 10^9$$$ for $$${i}={1}, {2}, \ldots, {N}$$$), where $$$A_i=-1$$$ indicates that the $$$i$$$-th element of the array needs to be determined, and a positive value is the actual $$$i$$$-th element of the array.

Output a single line with the uppercase letter "$$$\texttt{Y}$$$" if it is possible to complete the array with positive integers such that it becomes a beautiful mountain chain, and the uppercase letter "$$$\texttt{N}$$$" otherwise.

6
5 10 4 1 3 2

Y

11
5 10 4 -1 10 20 30 20 2 3 -1

Y

12
1 3 2 5 -1 8 9 -1 7 -1 4 5

N