M. Merge
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Siri is playing a WeChat mini-game that involves a two-player duel, so he called Dagu to play the game with him.

The game process is as follows: At the start of the game, both players are given a number of soldiers. Siri receives $$$n$$$ soldiers, the $$$i$$$-th of which with a combat power of $$$a_i$$$; Dagu also receives several soldiers. Each round, both sides summon one still-surviving soldier to fight. The side with the higher combat power will defeat the opponent's soldier and directly kill the opponent's general, winning the game. If the combat powers are equal, both soldiers die simultaneously and the next round begins. If all soldiers on both sides have fallen, the game is declared a draw.

To more easily win the game, Siri has installed a cheat that allows him to perform the following operation any number of times: merge two soldiers whose combat powers differ exactly by $$$1$$$ into a new soldier with a combat power equal to the sum of the original two soldiers' combat powers.

Clearly, in this game, sorting the sequence of each player's soldiers' combat powers in descending order, the player with the lexicographically larger sequence has a guaranteed winning strategy. Help Siri use the cheat to merge soldiers so that his sequence of soldiers' combat powers, when sorted in descending order, is lexicographically as large as possible. You only need to output the combat powers of the merged soldiers in any order.

A sequence $$$a = [a_1, a_2, \ldots, a_{|a|}]$$$ is lexicographically smaller than a sequence $$$b = [b_1, b_2, \ldots, b_{|b|}]$$$ if and only if at least one of the following is true:

  • $$$a$$$ is an empty sequence and $$$b$$$ is not an empty sequence.
  • Both $$$a$$$ and $$$b$$$ are not empty sequences and $$$a_1 \lt b_1$$$.
  • Both $$$a$$$ and $$$b$$$ are not empty sequences and $$$a_1 = b_1$$$ and $$$[a_2, a_3, \ldots, a_{|a|}]$$$ is lexicographically smaller than $$$[b_2, b_3, \ldots, b_{|b|}]$$$.
Input

The first line contains two integers $$$n$$$ ($$$1\le n\le 2\times 10^5$$$), representing the number of soldiers Siri has.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^{18}$$$), where the $$$i$$$-th integer $$$a_i$$$ represents the combat power of the $$$i$$$-th soldier among Siri's soldiers.

Output

The first line contains an integer $$$k$$$, representing the number of Siri's soldiers after merging.

The second line contains $$$k$$$ integers, representing the combat powers of Siri's soldiers after merging.

Examples
Input
4
1 2 3 4
Output
2
9 1
Input
5
2 3 3 4 4
Output
2
9 7
Input
4
1 2 2 4
Output
1
9
Note

In the first example, the optimal strategy is:

  • Merge $$$2,3$$$ to form $$$5$$$
  • Merge $$$4,5$$$ to form $$$9$$$

In the second example, the optimal strategy is:

  • Merge $$$2,3$$$ to form $$$5$$$
  • Merge $$$4,5$$$ to form $$$9$$$
  • Merge $$$3,4$$$ to form $$$7$$$

In the third example, the optimal strategy is:

  • Merge $$$1,2$$$ to form $$$3$$$
  • Merge $$$2,3$$$ to form $$$5$$$
  • Merge $$$4,5$$$ to form $$$9$$$