시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3838 876 578 22.622%

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

예제 입력 1

7
2
4
1
2
2
5
1

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjMwMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjRcdWM1NDRcdWMyZGNcdWMyYTQgXHVjN2FjXHVhY2IwXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM2MjRcdWM1NDRcdWMyZGNcdWMyYTRcdWM3NTggXHVjN2FjXHVhY2IwXHVkNTY5IFx1YWNmNVx1YzVmMFx1YzVkMCBOXHViYTg1XHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjMTFjXHVjMTFjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NCBcdWM1ZWRcdWMwYWNcdWM4MDFcdWM3NzggXHVjMjFjXHVhYzA0XHVjNzQ0IFx1YjlkZVx1Yzc3NFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjOTA0XHVjNWQwXHVjMTFjXHVjMTFjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIzNTggXHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1YWMxMVx1Yzc5MFx1YWUzMCBcdWM3OTBcdWFlMzBcdWFjMDAgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFkODFcdWFlMDhcdWQ1NzQgXHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHVjMGFjXHViNzhjIEFcdWM2NDAgQlx1YWMwMCBcdWMxMWNcdWI4NWMgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWI4MjRcdWJhNzQsIFx1YjQ1MCBcdWMwYWNcdWI3OGMgXHVjMGFjXHVjNzc0XHVjNWQwIEEgXHViNjEwXHViMjk0IEJcdWJjZjRcdWIyZTQgXHVkMGE0XHVhYzAwIFx1ZDA3MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNWM2XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjOTA0XHVjNWQwIFx1YzExY1x1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVkMGE0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzExY1x1Yjg1YyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMzMGRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5MDRcdWM1ZDBcdWMxMWMgXHVhZTMwXHViMmU0XHViOWFjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA1MDAsMDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NTggXHVkMGE0XHVhYzAwIFx1YjA5OFx1YjE3OFx1YmJmOFx1ZDEzMCBcdWIyZThcdWM3MDRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzU4IFx1ZDBhNFx1YjI5NCAyPHN1cD4zMTxcL3N1cD4gXHViMDk4XHViMTc4XHViYmY4XHVkMTMwIFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWMxMWMgXHVjNzg4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YzExY1x1Yjg1YyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMzMGRcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUEFUUklLIiwiZGVzY3JpcHRpb24iOiI8cD5OIHBlb3BsZSBhcmUgd2FpdGluZyBpbiBsaW5lIHRvIGVudGVyIGEgY29uY2VydC4gUGVvcGxlIGdldCBib3JlZCB3YWl0aW5nIHNvIHRoZXkgdHVybiBhbmQgbG9vayBmb3Igc29tZW9uZSBmYW1pbGlhciBpbiB0aGUgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VHdvIHBlcnNvbnMgQSBhbmQgQiBzdGFuZGluZyBpbiBsaW5lIGNhbiBzZWUgZWFjaCBvdGhlciBpZiB0aGV5JiMzOTtyZSBzdGFuZGluZyByaWdodCBuZXh0IHRvIGVhY2ggb3RoZXIgb3IgaWYgbm8gcGVyc29uIGJldHdlZW4gdGhlbSBpcyBzdHJpY3RseSB0YWxsZXIgdGhhbiBwZXJzb24gQSBvciBwZXJzb24gQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIHBlb3BsZSB0aGF0IGNhbiBzZWUgZWFjaCBvdGhlci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyA1MDAgMDAwKSwgdGhlIG51bWJlciBvZiBwZW9wbGUgc3RhbmRpbmcgaW4gbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciwgdGhlIGhlaWdodCBvZiBvbmUgcGVyc29uIGluIG5hbm9tZXRyZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5b25lIHdpbGwgYmUgc2hvcnRlciB0aGFuIDI8c3VwPjMxPFwvc3VwPiBuYW5vbWV0cmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaGVpZ2h0cyBhcmUgZ2l2ZW4gaW4gdGhlIG9yZGVyIGluIHdoaWNoIHBlb3BsZSBhcmUgc3RhbmRpbmcgaW4gbGluZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBwYWlycyBvZiBwZW9wbGUgdGhhdCBjYW4gc2VlIGVhY2ggb3RoZXIgb24gYSBzaW5nbGUgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d