시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB54131223.077%

문제

The Innopolis Open 2020 is coming. And this means that it’s time to order T-shirts for the participants of the Olympiad.

The organizers decided that it would be great to buy T-shirts of different colors so that you can easily see who is the organizer, jury or participant of the Olympiad.

For this task, two people were assigned, they decided how many T-shirts of each color should be ordered. However, they did not agree among themselves, and one of them wrote down the number of T-shirts of a certain color that needs to be ordered, and the other wrote the percentage of T-shirts of a certain color. As a result, they got a list of length $n$, where each element of the list $a_i$ is either the number of T-shirts of color $i$ or the percentage of T-shirts of color $i$ of the total number of T-shirts. Moreover, it is known that in the list at least one element $a_i$ is the number of T-shirts of the color $i$.

Now the organizers need to understand, what is the total of T-shirts they need to buy for the olympiad. Help them find all possible options for the total number of T-shirts for which such a list could be obtained.

입력

The first line contains a single integer $n$, the number of different colors ($1 \le n \le 10^5$).

The second line contains $n$ integers $a_i$, either the number of T-shirts or the percentage of t-shirts for the color $i$ ($1 \le a_i \le 10^9$).

출력

In the first line print the number of options for the total number of T-shirts for which such a list could be obtained.

In the second line print all possible options for the total number of T-shirts, in sorted order.

서브태스크

번호배점제한
113

$1 \le n \le 15$, $1 \le a_i \le 100$

221

$1 \le n \le 100$, $1 \le a_i \le 100$

338

$1 \le n \le 100$, $1 \le a_i \le 10^9$

428

$1 \le n \le 10^5$, $1 \le a_i \le 10^9$

예제 입력 1

2
1 50

예제 출력 1

2
2 51

예제 입력 2

3
20 30 70

예제 출력 2

4
120 125 140 300

예제 입력 3

4
2 40 90 5

예제 출력 3

3
137 470 840

예제 입력 4

7
10 20 5 15 30 17 3

예제 출력 4

1
100

힌트

Explanation of the first example:

If the total number of T-shirts is $2$: one of color $1$, and one of color $2$, we can obtain the given list if the first element ($1$) is the number of T-shirts of color $1$, and the second element ($50$) is the percentage of T-shirts of color $2$. $2 = 1 + 2 \cdot \frac{50}{100}$.

If the total number of T-shirts is $51$: one of color $1$, and $50$ of color $2$, we can obtain the given list, if both elements are the numbers of T-shirts of colors $1$ and $2$. $51 = 1 + 50$.

Explanation of the second example:

  • $120 = 20 + 30 + 70$
  • $125 = 125 \cdot \frac{20}{100} + 30 + 70$
  • $140 = 140 \cdot \frac{20}{100} + 140 \cdot \frac{30}{100} + 70$
  • $300 = 300 \cdot \frac{20}{100} + 30 + 300 \cdot \frac{70}{100}$

채점 및 기타 정보

  • 예제는 채점하지 않는다.