Description

Life is tough on the farm, and when life is tough you have to get tough. The cows have formed gangs (conveniently numbered $1$ to $M$). The gangs coexisted in peace for a while, but now things are really getting out of control.

The cows are competing for control of a great grazing field. This conflict happens over a series of minutes. Each minute a single cow walks into the field. If the field is empty, the new cow’s gang is considered to take control of the field. If the field is already controlled by the new cow’s gang, then the cow just starts grazing. Otherwise, a single cow from the controlling gang that is grazing confronts the new cow.

These confrontations between two cows start with some arguing and inevitably end with the pair realizing how much more alike than different they are. The cows, seeing the error in their ways, leave the gang and the field and get a cold glass of soy milk at FJ’s tavern. If, after this confrontation, the field is empty, then no gang controls the field.

Bessie realizes how these confrontations will occur. She knows how many cows are in each gang. Bessie really wants her gang to control the field after the conflict is over and all cows are either on the field or at FJ’s tavern. Help Bessie determine if it is possible for her gang, labeled $1$, to control the field in the end.

If it is possible, Bessie wants to know the maximum number of cows from her gang that could be on the field at the end. Output this number and the lexicographically earliest ordering of cows that results in this number of cows from Bessie’s gang at the end. An ordering $X$ is said to be lexicographically earlier than $Y$ if there is some $k$ such that $X[k] < Y[k]$ and $X[i] = Y[i]$ for all $i < k$.

There are $N$ cows split into $M$ gangs, and they are fighting over a pasture. Each unit of time, one cow arrives. If the pasture is empty or currently controlled by the arriving cow’s own gang, the cow stays. Otherwise, the arriving cow and one grazing cow from the controlling gang fight, and both leave to reflect at Farmer John’s tavern. Determine an arrival order of cow gang indices that maximizes the number of gang $1$ cows remaining on the field at the end. If this maximum is not $0$, also output the lexicographically smallest such ordering.

Input Format

• Line $1$: Two integers $N$ and $M$ ($1 \le N \le 100$, $1 \le M \le N$). The total number of cows across all gangs is $N$. The total number of gangs is $M$.
• Lines $2$ to $1+M$: The $(1+i)$-th line contains the number of members in gang $i$. Each gang has at least $1$ member.

Output Format

• Line $1$: Output YES if Bessie’s gang can control the field after the conflict; otherwise, output NO.
• Line $2$: If YES, output the maximum number of cows from Bessie’s gang that could be on the field at the end.
• Lines $3$ to $2+N$: If YES, output the lexicographically earliest ordering that achieves this maximum. On the $(i+2)$-th line, output the index of the gang of the cow that appears in the $i$-th minute.

5 3 
2 
1 
2 

YES 
1 
1 
3 
2 
3 
1 

Hint

There are $5$ cows and $3$ gangs. Bessie’s gang (gang $1$) has $2$ members, gang $2$ has $1$ member, and gang $3$ has $2$ members.

Only one cow from Bessie’s gang can end up on the field.

Translated by ChatGPT 5