#donuts20153. [donuts_2015_3]行列のできるドーナツ屋
[donuts_2015_3]行列のできるドーナツ屋
問題文
ドーナツ町には、毎日行列ができる超人気のドーナツ屋があります。このドーナツ屋には今 人の人がまっすぐ一列に並んでいます。行列に並んでいる人は、自分の番が来る前にドーナツが売り切れてしまうのではないかと不安に思っています。ドーナツ屋の店長は、それぞれの人がどれくらい不安に思っているのかを表す「不安度」を計算してみることにしました。
前から 番目 に並んでいる人を人 と呼ぶことにします。人 の身長は です。人 の「不安度」は「人 が前を見たときに見える人の数」です。人 が前を見たときに人 が見えるための条件は以下の通りです。
- 人 よりも 人 の方が前に並んでいる。すなわち、 である。
- 人 と人 の間に人 より身長の高い人がいない。すなわち、 かつ を満たすような が存在しない。
例えば、行列に並んでいる人の身長が前から順に なら、一番後ろに並んでいる人 が前を見たときに見える人は人 と人 の 人なので、人 の「不安度」は となります。
入力
入力は以下の形式で標準入力から与えられる。
...
- 行目には、行列に並んでいる人数を表す整数 が与えられる。
- 行目には、行列に並んでいる人の身長を表す 個の整数が空白区切りで与えられる。このうち 番目の整数 は、人 の身長を表す。ただし、 のとき であることが保証される。
部分点
この問題には部分点が設定されている。
- を満たすテストケースすべてに正解した場合は 点が与えられる。
- を満たすテストケースすべてに正解した場合は 点が与えられる。
出力
出力は 行からなる。このうち 行目には、人 の「不安度」を表す つの整数を出力せよ。出力の末尾にも改行を入れること。