Problem H
Trip Odometer

A trip odometer can be used to record the distance driven on a single trip. You are very diligent: at the start of each trip you reset the trip odometer to read $0$ and at the end of each trip you write down the distance travelled.

Thus, you maintain a list of distances (in kilometers) taken by all trips. Unfortunately, exactly one number from this list is spurious; you mistakenly recorded the length of one trip you took in another vehicle. You also forget which entry in your list corresponds to this trip.

You want to know all possible total distances that you could have taken in your own vehicle given that one of the written distances was fake. More specifically, all values $D$ such that it is possible to remove one trip from your list and have the remaining distances sum to $D$.


The first line of input contains a single integer $N$ ($2 \leq N \leq 10^5$), the number of distances you wrote down. The second line of input consists of $N$ integers $d_1, d_2, \ldots , d_ N$ ($1 \leq d_ i \leq 10^4$), where $d_ i$ is the length of the $i$th trip you recorded.


Display two lines. The first line should contain a single number $K$, which is the number of possible distinct distances that could be obtained. The second line should contain the list of the $K$ distinct integers, each of which is a possible sum that can be obtained by removing exactly one of the written distances. The list should be displayed in ascending order.

Sample Input 1 Sample Output 1
1 5 3 1
5 7 9
Sample Input 2 Sample Output 2
10 9 8 7 6
30 31 32 33 34
Sample Input 3 Sample Output 3
87 42 101 102 191 87 42
461 550 551 565 610
Sample Input 4 Sample Output 4
10 10 10 10 10

Please log in to submit a solution to this problem

Log in