Жүгіру клубы жаңа мүшелерді қабылдап, қарқынды дамып келеді: күн сайын клубқа дәл бір жаңа мүше қосылады. Әрбір мүше белгілі бір бастапқы шеберлік деңгейімен келеді және оларға келу ретіне қарай бірегей 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$-ші күні шеберлік деңгейлері $[1, 2, 3, 1, 2]$ болатын $5$ мүше бар. $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$-ші күні шеберлік деңгейлері $[1, 2, 3, 1, 2, 3, 2, 3]$ болатын $8$ мүше бар. Оңтайлы күш-жігерлер $[2, 1, 0, 2, 1, 0, 1, 0]$ және сәйкес максималды әлеуеттер $[4, 2, 0, 2, 1, 0, 0, 0]$.