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?
Constraints
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [30%]
No additional constraints.
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
.
Comments