ชมรมวิ่งแห่งหนึ่งกำลังเปิดรับสมาชิกใหม่และเติบโตอย่างรวดเร็ว โดยมีสมาชิกใหม่เข้าร่วมวันละหนึ่งคนพอดี สมาชิกแต่ละคนจะมีระดับทักษะเริ่มต้นที่แน่นอน และจะได้รับ ID เฉพาะตามลำดับการเข้าร่วม

ในตอนท้ายของทุกวัน โค้ชมักจะคำนวณตัวชี้วัดที่เขาเรียกว่า "ศักยภาพรวม" ของชมรม ค่านี้คือผลรวมของศักยภาพส่วนบุคคลของสมาชิกปัจจุบันทั้งหมด เพื่อสร้างแรงจูงใจให้สมาชิก ศักยภาพของสมาชิกแต่ละคนจะถูกคำนวณผ่านสถานการณ์สมมติว่ามีการฝึกซ้อมอย่างหนักเพียงครั้งเดียว

ในการฝึกซ้อมสมมตินี้ สมาชิกสามารถเลือกที่จะทุ่มเทความพยายามจำนวนหนึ่งเพื่อเพิ่มระดับทักษะของตนชั่วคราว ทุกๆ $1$ หน่วยของความพยายามที่ใช้ไป ระดับทักษะของเขาจะเพิ่มขึ้น $1$ หน่วยพอดี เป็นการตอบแทน เขาจะได้รับ "ความสุข" $1$ หน่วยสำหรับสมาชิกคนอื่นๆ ที่อยู่ในชมรมในขณะนั้นแต่ละคนซึ่ง:

• เข้าร่วมชมรมหลังจากเขาอย่างแท้จริง และ
• เดิมทีมีระดับทักษะสูงกว่าเขาอย่างแท้จริง แต่ตอนนี้ถูกไล่ทันหรือแซงหน้าไปแล้วเนื่องจากการฝึกซ้อมนี้

สังเกตว่าในระหว่างการคำนวณนี้ มีเพียงระดับทักษะของสมาชิกคนนั้นเท่านั้นที่เพิ่มขึ้น ในขณะที่ระดับทักษะของสมาชิกคนอื่นๆ ทั้งหมดยังคงเดิมตามค่าเริ่มต้น

ศักยภาพของสมาชิกหนึ่งคนถูกนิยามว่าเป็นค่าสูงสุดที่เป็นไปได้ของผลตอบแทนสุทธิ (ความสุขลบด้วยความพยายาม) ที่เขาสามารถทำได้โดยการเลือกระดับความพยายามอย่างเหมาะสมที่สุด การฝึกซ้อมเหล่านี้เป็นเพียงทฤษฎีเท่านั้น ใช้สำหรับรายงานประจำวันของโค้ชเท่านั้น และระดับทักษะที่แท้จริงของสมาชิกจะไม่เปลี่ยนแปลงในแต่ละวัน

งานของคุณคือช่วยโค้ชคำนวณศักยภาพรวมของชมรมในตอนท้ายของแต่ละวันในช่วงเปิดรับสมาชิก

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 10^5$) แทนจำนวนวันที่ชมรมเปิดรับสมาชิก

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) โดยที่ $a_i$ คือระดับทักษะเริ่มต้นของสมาชิกที่เข้าร่วมในวันที่ $i$

ข้อมูลส่งออก

แสดงผลจำนวนเต็ม $n$ จำนวนในบรรทัดเดียว จำนวนเต็มลำดับที่ $k$ คือศักยภาพรวมของชมรมในตอนท้ายของวันที่ $k$

ตัวอย่าง

ข้อมูลนำเข้า 1

8
1 2 3 1 2 3 2 3

ข้อมูลส่งออก 1

0 0 0 0 1 3 5 9

ข้อมูลนำเข้า 2

1
1

ข้อมูลส่งออก 2

0

หมายเหตุ

คำอธิบายตัวอย่างที่ 1: ในวันที่ $5$ มีสมาชิก $5$ คนที่มีระดับทักษะ $[1, 2, 3, 1, 2]$ สำหรับสมาชิกคนที่ $1$: มีสมาชิก $3$ คนที่เข้าร่วมทีหลังและมีทักษะสูงกว่าอย่างแท้จริง ได้แก่ สมาชิกคนที่ $2$, สมาชิกคนที่ $3$ และสมาชิกคนที่ $5$ ศักยภาพสูงสุดของสมาชิกคนที่ $1$ คือ $1$ ซึ่งทำได้โดยกลยุทธ์ใดกลยุทธ์หนึ่งต่อไปนี้:

• หากสมาชิกคนที่ $1$ ใช้ความพยายาม $1$ หน่วย ทักษะของเขาจะกลายเป็น $2$ เขาจะไล่ทันหรือแซงหน้าสมาชิกคนที่ $2$ และสมาชิกคนที่ $5$ ความสุขที่ได้คือ $2$ หน่วย และผลตอบแทนสุทธิคือ $2 - 1 = 1$ หน่วย
• หากสมาชิกคนที่ $1$ ใช้ความพยายาม $2$ หน่วย ทักษะของเขาจะกลายเป็น $3$ เขาจะไล่ทันหรือแซงหน้าสมาชิกคนที่ $2$, $3$ และ $5$ ความสุขที่ได้คือ $3$ หน่วย และผลตอบแทนสุทธิคือ $3 - 2 = 1$ หน่วย

สมาชิกคนอื่นๆ มีศักยภาพสูงสุดเป็น $0$ ดังนั้น ศักยภาพรวมสำหรับวันที่ $5$ คือ $1$

ในวันที่ $8$ มีสมาชิก $8$ คนที่มีระดับทักษะ $[1, 2, 3, 1, 2, 3, 2, 3]$ ความพยายามที่เหมาะสมที่สุดคือ $[2, 1, 0, 2, 1, 0, 1, 0]$ และศักยภาพสูงสุดที่สอดคล้องกันคือ $[4, 2, 0, 2, 1, 0, 0, 0]$