Which elements can be deleted? If is the minimum in a segment of length at least two, it has an immediate neighbor inside that segment, and that neighbor is larger. Conversely, a larger immediate neighbor allows us to choose that pair and delete . Thus an element can be deleted exactly when its current left or right neighbor is larger.
Order of retained positions Operations only delete elements, so must be a subsequence of . Let be the original position of value . Check
This also rejects repeated values in .
Condition for a gap Retained elements are never deleted. The elements to delete therefore form independent gaps: before the first retained element, between consecutive retained elements, and after the last one. Elements from different gaps cannot become adjacent across a retained element.
For a nonempty gap, let be its maximum and the larger of its adjacent retained boundary values. An end gap has only one boundary. The gap can be completely deleted if and only if .
Necessity: deleting requires a larger neighbor. None exists inside the gap, so such a neighbor must be a retained boundary, implying .
Sufficiency: delete gap elements in increasing order. While at least two remain, the smallest remaining element has a larger neighbor in the same gap and can be deleted. When only remains, it is adjacent to a boundary of value and can also be deleted. Empty gaps automatically satisfy the condition.
Implementation Visit retained elements in order and scan each preceding gap once to find its maximum. Use zero as the missing left boundary and as the maximum of an empty gap. Since real values are positive, the same comparison handles these cases. Check the final suffix separately.
Print YES exactly when the position order and every gap condition hold. The global maximum cannot be deleted, so an missing is always rejected. However, neither containing nor being a subsequence is sufficient. For example, and satisfy both properties but cannot delete between boundaries .
Time and space are . All positions, values, and gap maxima are at most ; no large arithmetic is needed.
Subtask 1 represents retained positions by a bitmask and uses BFS over all legal segment operations. There are at most states. Incrementally maintaining each interval minimum enumerates the operations of one state in time. Total time is and space is , sufficient for . Subtask 2 uses the linear check above.
Solution written by GPT6