Description
著名樂(lè)隊(duì)L2B宣布要在Music島舉辦一場(chǎng)演唱會(huì)，售票當(dāng)天那家伙，那場(chǎng)面，相當(dāng)熱鬧，真是鑼鼓喧天，鞭炮齊鳴，旌旗招展，人山人海啊。
L2B的粉絲小C得知消息，飛奔到售票處，卻發(fā)現(xiàn)買(mǎi)票的人已經(jīng)排起了長(zhǎng)龍的隊(duì)伍，正當(dāng)他萬(wàn)般絕望的時(shí)候，他看到了敬愛(ài)的PengSir，于是他向PengSir請(qǐng)求幫助。PengSir嘴角微微一笑，說(shuō)道：票我倒是可以給你一張，可是白給的話就太沒(méi)意思了，這樣吧，我有一個(gè)問(wèn)題考考你，如果你能在5秒鐘內(nèi)答出來(lái)的話，我就送你這張票，怎么樣？小C急不可待的說(shuō)：沒(méi)問(wèn)題。于是PengSir徐徐說(shuō)道：這里排隊(duì)的一共有N個(gè)人，每個(gè)人之前都發(fā)了一個(gè)號(hào)碼牌（數(shù)字從1到N各不相同），我們假定隊(duì)頭是前，隊(duì)尾是后，每個(gè)人P最多能夠買(mǎi)的票數(shù)是在這個(gè)人后面而且號(hào)碼牌的數(shù)字比這個(gè)人P的數(shù)字小的人數(shù)總和。我的問(wèn)題是，告訴你每個(gè)人手中的號(hào)碼，你來(lái)算出今天最多一共能賣(mài)出去多少?gòu)埰盨么？
舉個(gè)例子說(shuō)吧
假設(shè)我們現(xiàn)在有10個(gè)人在排隊(duì)，他們手中的號(hào)碼分別是2 5 8 7 6 1 9 4 10 3，那么可以很快算出他們最多可以買(mǎi)的票數(shù)分別是1 3 5 4 3 0 2 1 1 0，所以最多一共能賣(mài)出去1+3+5+4+3+0+2+1+1+0=20張票。怎么樣？明白了吧？
小C聽(tīng)完，頓時(shí)傻眼，親愛(ài)的朋友，你能幫助小C來(lái)實(shí)現(xiàn)自己心愿嗎？
Input
輸入有多個(gè)測(cè)試用例
每個(gè)測(cè)試用例的第一行是正數(shù)N（ 0 < N <= 30000 ），
第二行是N個(gè)整數(shù)Ai（ 0 < Ai <= N ），且每個(gè)Ai出現(xiàn)且僅出現(xiàn)一次，每?jī)蓚€(gè)相鄰的整數(shù)之間有且僅有一個(gè)空格隔開(kāi)
Output
對(duì)于每一個(gè)測(cè)試用例，只輸出一個(gè)整數(shù)S
Sample Input
Sample Output