თანაბარი რიცხვების შეერთება

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: codeforces, 962D


მოცემული გვაქვს დადებითი რიცხვების მასივი. სანამ მასივში ორი მაინც თანაბარი ელემენტია, ვასრულებთ შემდეგ ოპერაციას: ვირჩევთ უმცირეს x მნიშვნელობას რომელიც მასივში გვხვდება 2 ან მეტჯერ. ვიღებთ მასივში x-ის პირველ ორ შემთხვევას (ორ ყველაზე მარცხნივ მდგომს). ამ ორი ელემენტიდან მარცხნივ მდგომი იშლება, ხოლო მარჯვნივ მდგომი ჩანაცვლდება ამ ელემენტების ჯამით (რომელიც გამოდის: 2 ⋅ x).

დაადგინეთ როგორი სახე ექნება მასივს ზემოთ აღწერილი მოქმედებების შესრულების შემდეგ.

მაგალითისთვის, თუ მასივი გამოიყურება როგორც - [3,4,1,2,2,1,1]. იგი შეიცვლება შემდეგნაირად: [3,4,1,2,2,1,1] → [3,4,2,2,2,1] → [3,4,4,2,1] → [3,8,2,1]. თუ თავდაპირველი მასივი გამოიყურება როგორც - [1,1,3,1,1], იგი საბოლოოდ მიიღებს შემდეგ სახეს: [1,1,3,1,1] → [2,3,1,1] → [2,3,2] → [3,4].

 

შესატანი მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი n(2≤n≤150 000) – ელემენტთა რაოდენობა მასივში.  მომდევნო სტრიქონი n რაოდენობის ელემენტი a1,a2,…,an (1 ≤ ai ≤ 109) – მასივის ელემენტები.

გამოსატანი მონაცემები: პირველ ხაზზე მთელი რიცხვი k – ელემენტების რაოდენობა მასივში ყველა ოპერაციის შემდეგ. მეორე ხაზზე k მთელი რიცხვი – მასივის ელემენტები ყველა ოპერაციის შესრულების შემდეგ.

 

 




მაგალითები

შესატანი მონაცემები
7 3 4 1 2 2 1 1 დაკოპირება
გამოსატანი მონაცემები
4 3 8 2 1 დაკოპირება