Շոկոլադի Խանութը

Քանի որ խանութի դիմաց կանգնած են n մարդիկ, և խանութը վաճառում է միայն շոկոլադ, ամեն անգամ, երբ հաճախորդը մտնում է խանութ, խանութը ստանում է 1 կգ շոկոլադ: Հաճախորդին հասնելիս խանութը կարող է վաճառել այդ 1 կգ շոկոլադը։
Մենք գիտենք, թե քանի կգ շոկոլադ է ցանկանում գնել հերթում կանգնած յուրաքանչյուր մարդ։ Եթե հաճախորդը ներս է մտնում, բայց խանութում բավարար շոկոլադ չի լինում, նա վերադառնում է հերթի վերջ և սպասում, մինչև նորից փորձի։ Իսկ եթե հաճախորդը կարողանում է ձեռք բերել իրեն անհրաժեշտ շոկոլադը, նա ստանում է այն ու դուրս գալիս խանութից։
Ձեզ խնդրում են պարզել, թե քանի անգամ ամեն մարդ կմտնի խանութ, որպեսզի վերջապես գնի իր ուզած շոկոլադի քանակը։
Սկզբում խանութը շոկոլադ չունի։

Մուտք

Մուտքի առաջին տողում տրված է n ամբողջ թիվը (1 ≤ n ≤ 10 000)։
Հաջորդ տողում նշված են n ամբողջ թվեր, որոնք ներկայացնում են յուրաքանչյուր հաճախորդի պահանջվող շոկոլադի քանակը (1 ≤ ≤ 20)։

Ելք

Ծրագիրը պետք է տպի n ամբողջ թվեր, որոնցից Յուրաքանչյուր թիվ ցույց է տալիս, թե քանի անգամ տվյալ հաճախորդը մտավ խանութ։

Օրինակներ

Մուտք
Ելք
3 1 3 2
1 4 1

Բացատրություն

  1. Առաջին հաճախորդը մտնում է խանութ → խանութը ստանում է 1 կգ շոկոլադ ⇒ բավարարում է հաճախորդի պահանջը, և հաճախորդը հեռանում է։
  1. Երկրորդ հաճախորդը մոտենում է → խանութը ստանում է 1 կգ շոկոլադ, սակայն հաճախորդին 3 կգ է պետք, ուստի նա վերադառնում է հերթի վերջ։
  1. Երրորդ հաճախորդը մտնում է խանութ → խանութը ստանում է ևս 1 կգ շոկոլադ (ընդամենը 2 կգ) ⇒ բավարարում է նրա 2 կգ պահանջը, ու հաճախորդը հեռանում է։
  1. Երկրորդ հաճախորդը կրկին մտնում է խանութ → խանութը ստանում է 1 կգ շոկոլադ, խանութում այժմ միայն 1 կգ է, իսկ հաճախորդին պետք է 3, հետևաբար նա դուրս է գալիս։
  1. Երկրորդ հաճախորդը նորից է մտնում խանութ → խանութը ստանում է 1 կգ շոկոլադ, այժմ ունենք 2 կգ, և դարձյալ չի բավականացնում 3 կգ պահանջը, հաճախորդը կրկին դուրս է գալիս։
  1. Երկրորդ հաճախորդը էլի է մտնում խանութ → խանութը ստանում է 1 կգ շոկոլադ (ընդամենը 3 կգ) ⇒ բավարարում է հաճախորդի պահանջը, ու նա վերջապես հեռանում է։
Արդյունքում, առաջին հաճախորդը խանութ է մտել 1 անգամ, երկրորդը՝ 4 անգամ, իսկ երրորդը՝ 1 անգամ։

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue