You are given an array of positive integers. While there are at least two equal elements, we will perform the following operation. We choose the smallest value $x$ that occurs in the array $2$ or more times. Take the first two occurrences of $x$ in this array (the two leftmost occurrences). Remove the left of these two occurrences, and the right one is replaced by the sum of this two values (that is, $2 \cdot x$).

Determine how the array will look after described operations are performed.

For example, consider the given array looks like $[3, 4, 1, 2, 2, 1, 1]$. It will be changed in the following way: $[3, 4, 1, 2, 2, 1, 1]~\rightarrow~[3, 4, 2, 2, 2, 1]~\rightarrow~[3, 4, 4, 2, 1]~\rightarrow~[3, 8, 2, 1]$.

If the given array is look like $[1, 1, 3, 1, 1]$ it will be changed in the following way: $[1, 1, 3, 1, 1]~\rightarrow~[2, 3, 1, 1]~\rightarrow~[2, 3, 2]~\rightarrow~[3, 4]$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 150\,000$) — the number of elements in the array.

The second line contains a sequence from $n$ elements $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{9}$) — the elements of the array.


-----Output-----

In the first line print an integer $k$ — the number of elements in the array after all the performed operations. In the second line print $k$ integers — the elements of the array after all the performed operations.


-----Examples-----
Input
7
3 4 1 2 2 1 1

Output
4
3 8 2 1 

Input
5
1 1 3 1 1

Output
2
3 4 

Input
5
10 40 20 50 30

Output
5
10 40 20 50 30 



-----Note-----

The first two examples were considered in the statement.

In the third example all integers in the given array are distinct, so it will not change.

Difficulty: interview

Starter code:

Solutions:
n = int(input())

xs = [int(x) for x in input().split()]

pos = {}
for i, x in enumerate(xs):
    while x in pos:
        del pos[x]
        x *= 2
    pos[x] = i

ks = sorted(list(pos.keys()), key=lambda k: pos[k])

print(len(ks))
print(" ".join(map(str, ks)))


import heapq
n = int(input())
A = list(map(int, input().split()))
hq = []
for i in range(n):
  heapq.heappush(hq, (A[i], i))
while len(hq) >= 2:
  t1 = heapq.heappop(hq)
  t2 = heapq.heappop(hq)
  if t1[0] == t2[0]:
    A[t1[1]] = 0
    A[t2[1]] = 2 * t1[0]
    heapq.heappush(hq, (2 * t2[0], t2[1]))
  else:
    heapq.heappush(hq, t2)
print(len(A) - A.count(0))
for a in A:
  if a != 0:
    print(a, end=' ')


n=int(input())
def insert(x,d,i,s):
    s.add(x)
    try:
        d[x].append(i)
        if(len(d[x])==2):
            d[x]=[]
            s.remove(x)
            insert(2*x,d,i,s)
    except:
        d[x]=[i]




a=list(map(int,input().split()))

d=dict()
s=set()

for i in range(n):
    insert(a[i],d,i,s)
fin=[]
#print(d)
#print(s)
for i in d.keys():
    for j in d[i]:
        fin.append([j,i])
fin.sort()
#print(fin)
print(len(fin))
for i in fin:
    print(i[1],end=' ')
    




n = int(input())
L = input().split(' ')
for i in range(len(L)):
    L[i] = int(L[i])
dico = {}
j = 0
while j < len(L):
    if L[j] not in dico or dico[L[j]] == -1:
        dico[L[j]] = j
        j += 1
    else:
        L[dico[L[j]]] = -1
        dico[L[j]] = -1
        L[j] = L[j] * 2
sm = 0
for i in range(len(L)):
    if L[i] != -1:
        sm += 1
print(sm)
k = 1
for i in range(len(L)):
    if L[i] != -1:
        if k < sm:
            print(L[i], end=' ')
        else:
            print(L[i])
        k += 1


from collections import deque

N = int(input())
A = list(map(int, input().split()))

# index = [-1] * (sum(A)+1)
#
# for i in range(N):
#     while index[A[i]] != -1:
#         A[index[A[i]]] = -1     # -1 は delete
#         index[A[i]] = -1        # A[i] はなくなった
#         A[i] *= 2
#     index[A[i]] = i

dic = dict()

for i in range(N):
    while A[i] in dic:
        A[dic[A[i]]] = -1     # -1 は delete
        del dic[A[i]]        # A[i] はなくなった
        A[i] *= 2
    dic[A[i]] = i

B = []
for a in A:
    if a > 0:
        B.append(a)
print(len(B))
print(" ".join(list(map(str, B))))

def merge(a,b):
    la=len(a)
    lb=len(b)
    i=0
    j=0
    ans=[]
    while i<la and j<lb:
        if a[i]<b[j]:
            ans.append(a[i])
            i+=1
        else:
            ans.append(b[j])
            j+=1
    while i<la:
        ans.append(a[i])
        i+=1
    while j<lb:
        ans.append(b[j])
        j+=1
    return ans
n=int(input())
a=list(map(int,input().strip().split()))
d={}
for i in range(n):
    if a[i] in d:
        d[a[i]].append(i)
    else:
        d[a[i]]=[i]
x=[]
y=[]
for i in d:
    x.append(i)
x.sort()
lx=len(x)
ly=0
i=0
j=0
ans={}
while i<lx or j<ly:
    r=0
    if i>=lx:
        r=y[j]
        j+=1
    elif j>=ly:
        r=x[i]
        i+=1
    else:
        if x[i]<y[j]:
            r=x[i]
            i+=1
        else:
            r=y[j]
            j+=1
    l=len(d[r])
    if l%2!=0:
        ans[d[r][-1]]=r
    if l==1:
        continue
    temp=[]
    for rj in range(1,l,2):
        temp.append(d[r][rj])
    if 2*r in d:
        d[2*r]=merge(d[2*r],temp)
    else:
        d[2*r]=temp
        y.append(2*r)
        ly+=1
x=[]
for i in ans:
    x.append(i)
x.sort()
print(len(x))
for i in x:
    print(ans[i],end=' ')
    
        
        

    



    
    
    

n=int(input())
arr=list(map(int,input().strip().split(' ')))
d={}
i = 0
while(i<n):
  try:
    t = d[arr[i]]
    arr[t] = -1
    del d[arr[i]]
    arr[i] = 2*arr[i]
  except KeyError:
    d[arr[i]] = i
    i+=1
print(n-arr.count(-1))
for i in range(n):
  if(arr[i]!=-1):
    print(arr[i],end=' ')



n=int(input())
out=n
L=list(map(int,input().split()))
X=dict()

def f(x):
    try:
        return X[x]
    except:
        return -1

for i in range(n):
    x=L[i];
    while (f(x)!=-1):
        L[X[x]]=-1
        out-=1
        X[x]=-1
        L[i]*=2
        x=L[i]
    X[x]=i
print(out)
for i in range(n):
    if (L[i]!=-1):
        print(L[i],end=" ")
print()


n = int(input())
a = list(map(int, input().split()))

c = {}

for p in range(len(a)):
    while c.get(a[p], -1) >= 0:
        a[c[a[p]]] = 0
        c[a[p]] = -1
        a[p] *= 2

    c[a[p]] = p

solution = [str(x) for x in a if x > 0]
print(len(solution))
print(' '.join(solution))

n=int(input().split()[0])
ns=[int(x) for x in input().split()[:n]]
ind={}
i=0
while i<n:
    ni=ns[i]
    while ni in ind:
        ns[ind[ni]]=None
        ind.pop(ni, None)
        ni*=2
    ns[i]=ni
    ind[ni]=i
    i+=1
ans=[x for x in ns if x!=None]
print(len(ans))
for i in ans:
    print(i,end=' ')



import sys
import math
import itertools
import heapq
import bisect

def solution(n,arr):

    count = {}
    for i,num in enumerate(arr):
        if num in count:
            heapq.heappush(count[num], i)
        else:
            count[num] = [i]

    pq = []
    for num,c in count.items():
        occs = len(c) 
        if occs >= 2:
            heapq.heappush(pq, num)

    while pq:
        num = heapq.heappop(pq)
        if len(count[num]) < 2:
            continue
        i = heapq.heappop(count[num])
        j = heapq.heappop(count[num])
        arr[i] = None
        arr[j] = num * 2
        if num * 2 in count:
            heapq.heappush(count[num*2], j)
            if len(count[num*2]) >= 2:
                heapq.heappush(pq, num*2)
        else:
            count[num * 2] = [j]
        if len(count[num]) >= 2:
            heapq.heappush(pq, num)

    res = [str(ai) for ai in arr if ai != None]
    print(len(res))
    print(' '.join(res))

n = sys.stdin.readline().strip()
arr = list(map(int, sys.stdin.readline().strip().split(' ')))
solution(n,arr)

import sys
import math
import itertools
import heapq
import bisect

def solution(n,arr):

    count = {}
    for i,num in enumerate(arr):
        if num in count:
            heapq.heappush(count[num], i)
        else:
            count[num] = [i]

    pq = []
    for num,c in count.items():
        occs = len(c) 
        if occs >= 2:
            heapq.heappush(pq, num)

    while pq:
        num = heapq.heappop(pq)
        if len(count[num]) < 2:
            continue
        i = heapq.heappop(count[num])
        j = heapq.heappop(count[num])
        arr[i] = None
        arr[j] = num * 2
        if num * 2 in count:
            heapq.heappush(count[num*2], j)
            if len(count[num*2]) >= 2:
                heapq.heappush(pq, num*2)
        else:
            count[num * 2] = [j]
        if len(count[num]) >= 2:
            heapq.heappush(pq, num)

    res = [str(ai) for ai in arr if ai != None]
    print(len(res))
    print(' '.join(res))

n = sys.stdin.readline().strip()
arr = list(map(int, sys.stdin.readline().strip().split(' ')))
solution(n,arr)

def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    idx = {}
    for i in range(len(a)):
        x = a[i]
        while x in idx:
            del idx[x]
            x *= 2
        # there is no any pair of equal number in idx
        # so every time when updating idx, i is the right place to record x
        idx[x] = i

    ans = list(sorted(idx.keys(), key=lambda x: idx[x]))
    print(len(ans))
    print(' '.join([str(x) for x in ans]))


def __starting_point():
    main()
__starting_point()

n = int(input())
nums = list(map(int, input().split()))

# traverse array --- note we only modify right terms
lastSeen = {}
i = 0
while i < len(nums):
    if nums[i] in lastSeen:
        nums[lastSeen[nums[i]]] = 0  # ignore the num at this index
        del lastSeen[nums[i]]
        nums[i] <<= 1
        i -= 1
    else:
        lastSeen[nums[i]] = i
    i += 1

newnums = []
for n in nums:
    if n != 0:
        newnums.append(n)

print(len(newnums))
print(' '.join(map(str, newnums)))


n = int(input())
a = list(map(int, input().split()))

idx = {}
for i in range(n):
    x = a[i]
    while x in idx:
        del idx[x]
        x *= 2
    idx[x] = i


print(len(idx))
print(*list(idx.keys()))


n=int(input())
def insert(x,d,i,s):
    s.add(x)
    try:
        d[x].append(i)
        if(len(d[x])==2):
            d[x]=[]
            s.remove(x)
            insert(2*x,d,i,s)
    except:
        d[x]=[i]




a=list(map(int,input().split()))

d=dict()
s=set()

for i in range(n):
    insert(a[i],d,i,s)
fin=[]
#print(d)
#print(s)
for i in d.keys():
    for j in d[i]:
        fin.append([j,i])
fin.sort()
#print(fin)
print(len(fin))
for i in fin:
    print(i[1],end=' ')
    


import math
n=int(input())
arr=list(map(int,input().split()))
tb={}
#arr=sorted(arr)

for i in range(n):
    #print(i)
    if arr[i] in tb:
        x=arr[i]
        while x in tb:
            y=tb.pop(x)
            if 2*x not in tb:
                tb[2*x]=i
                break
            x=2*x
    else:
        tb[arr[i]]=i
    #print(tb)

#print(tb)
s=''
print(len(tb))
key=list(tb.keys())
ans=[]
for i in key:
    ans.append([tb[i],i])

ans.sort()

for i in ans:
    s+=str(i[1])+" "

##
##key=sorted(list(tb.keys()))
##i=0
##while j>=0:
##    for i in range(len(key)):
##        if key[i]%arr[j]==0:
##            x=key[i]//arr[j]
##            val=math.log(x,2)
##            if int(val)==val:
##                s=str(key[i])+' '+s
##                key[i]=-1
##                print(arr[j],s)
##                break
##    j-=1
##

##while len(tb)>0:
##    if arr[j] in tb:
##        s=str(arr[j])+' '+s
##        g=tb.pop(arr[j])
##    else:
##        x=arr[j]
##        c=0
##        while (x not in tb and c<100):
##            #print(tb,x)
##            x=2*x
##            c+=1
##        if c<100:
##            s=str(x)+' '+s
##            g=tb.pop(x)
##    j-=1

print(s)


def read_data():
    n = int(input().strip())
    a = list(map(int, list(input().strip().split())))
    return n, a

def solve():
    s = {}
    for i in range(len(a)):
        j = a[i]
        while j in s:
            del s[j]
            j *= 2
        s[j] = i

    sol = list(sorted(s.keys(), key=lambda j: s[j]))
    print(len(sol))
    print(*sol)

n, a = read_data()
solve()

n = int(input())
a = [int(x) for x in input().split()]


repeats = {}
for i, v in enumerate(a):
    x = v
    while x in repeats:
        del repeats[x]
        x *= 2
    repeats[x] = i
    
print(len(repeats))
print(*repeats.keys())

n = int(input())
a = list(map(int, input().split()))

idx = {}
for i in range(n):
	x = a[i]
	while x in idx:
		del idx[x]
		x *= 2
	idx[x] = i
	
print(len(idx))
print(*list(idx.keys()))

n=int(input())
ns=[int(x) for x in input().split()]
ind={}
for i in range(n):
    ni=ns[i]
    while ni in ind:
        ns[ind[ni]]=None
        ind.pop(ni, None)
        ni*=2
    ns[i]=ni
    ind[ni]=i
ans=[str(x) for x in ns if x!=None]
print(len(ans))
print(' '.join(ans))

def inpmap():
    return list(map(int, input().split()))
n = int(input())
arr = list(inpmap())

dc = {}
for i in range(n):
    x = arr[i]
    while x in dc:
        del dc[x]
        x *= 2
    dc[x] = i
print(len(dc))
print(*dc)


n = int(input())
a = list(map(int , input().split()))
idx = {}
for i in range(n):
    x = a[i]
    while x in idx:
        del idx[x]
        x *= 2
    idx[x] = i
print(len(idx))
print(*list(idx.keys()))