## The Contest Contest 1 P4 - A Typical YAC Problem

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Josh lives on a street with houses conveniently numbered from to from left to right, where Josh lives at house number . Nils doesn't know what is, but Josh tells him that he'll be going for a walk.

Starting from his house , he will repeatedly travel along the street to adjacent houses, never going to the left of house or to the right of house . His walk ends back at his house , though he can pass by his house multiple times during the walk. Let be the list of house numbers that Josh visited on his walk, in order.

Nils also knows that Josh never visits more than consecutive houses in a row. More formally, if is a monotonic subarray of , then . Note that an array is monotonic if the elements are either all strictly increasing or all strictly decreasing.

After going on his walk, he constructs an array , where is the number of times he visited house number during his walk.

Confident that his address is hidden, Josh gives Nils . Using this array, can you help Nils determine Josh's possible house numbers, or determine that the array is inconsistent?

#### Input Specification

The first line contains two integers and .

The next line contains integers .

#### Output Specification

First output a line containing an integer , the number of possible house numbers .

If , output distinct integers, the possible house numbers on the next line in ascending order.

#### Sample Input 1

4 4
1 3 3 2

#### Sample Output 1

2
2 4

#### Explanation for Sample 1

A possible walk Josh could have taken is , which starts and ends at house . In this walk, the longest monotonic subarray is , which has a length of .

Another possible walk Josh could have taken is , which starts and ends at house .

#### Sample Input 2

5 3
2 2 2 2 1

#### Sample Output 2

0

#### Explanation for Sample 2

There are no possible paths that satisfy the given constraints. Even though is a path that starts and ends at house , it does not satisfy the constraints since the monotonic subarray has a length greater than .