## DMOPC '21 Contest 8 P6 - Castle Building

View as PDF

Points: 40 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

Billy is playing with his newly bought Lego set containing blocks with distinct heights from to . He would like to build a castle with these blocks, which involves arranging the blocks in a row where the heights from left to right are such that there is some index where the heights are strictly increasing from to and strictly decreasing from to . Formally, .

To help guide him, Billy found an old, worn out instruction manual from the bottom of his bed. The instructions give the required heights of each building block from left to right. However, some of these numbers are so smudged that he cannot determine what they are! These are denoted with . Furthermore, Billy revises his interpretation of the instructions times, where he assumes that the number at index is actually .

Perplexed, Billy runs to you for help. Initially and after each of the revisions, tell Billy if there exists a castle consistent with the instructions.

#### Constraints

Initially and after each of the revisions, the instructions contain no duplicates of positive values.

#### Input Specification

The first line contains integers and .

The next line contains integers, the initial instructions .

Each of the next lines contains the description of a revision, integers and .

#### Output Specification

Initially and after each of the revisions, output YES if there exists a castle consistent with the instructions and NO otherwise.

#### Sample Input

9 3
1 0 0 5 0 0 8 0 2
5 9
7 0
5 0

#### Sample Output

YES
NO
YES
YES

#### Explanation

Initially, 1 3 4 5 7 9 8 6 2 is a possible castle.

After the first revision, the instructions are 1 0 0 5 9 0 8 0 2, which has no consistent castle.

After the second revision, the instructions are 1 0 0 5 9 0 0 0 2, and 1 3 4 5 9 8 7 6 2 is a possible castle.

After the third revision, the instructions are 1 0 0 5 0 0 0 0 2, which has a few possible castles.