시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 793 278 203 38.815%

문제

sook-001(1).jpg

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호
  • 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
  • 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
  • 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
  • 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
  • 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
  • 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

입력

  • 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
  • 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

  • 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

예제 입력 1

6
10
3
7
4
12
2

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjYxOTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjVcdWMwYzEgXHVjODE1XHVjNmQwIFx1YWZiOFx1YmJmOFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJzb29rLTAwMSgxKS5qcGdcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9jYTQ1OGYwNy1kM2IzLTQzNmYtYTk5Ni00OTA4MDkzNTE0OWFcLy1cL3ByZXZpZXdcL1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWIzYzRcdWMyZGNcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWJlNGNcdWI1MjlcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJlNGNcdWI1MjkgXHVhZDAwXHViOWFjXHVjNzc4XHViNGU0XHVjNzQwIFx1YjllNFx1YzZiMCBcdWMxMzFcdWMyZTQgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViMmU0XHViOTc4IFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWM2MjVcdWMwYzEgXHVjODE1XHVjNmQwXHVjNzQ0IFx1YmNhNFx1Y2U1OFx1YjljOFx1ZDBiOSBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5pXHViYzg4XHVjOWY4IFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWQwYTRcdWFjMDAgaDxzdWI+aTxcL3N1Yj5cdWM3NzRcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWJlNGNcdWI1MjlcdWM3NDAgXHVjNzdjXHViODJjXHViODVjIFx1YzExYyBcdWM3ODhcdWFjZTAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjXHViOWNjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5pXHViYzg4XHVjOWY4IFx1YmU0Y1x1YjUyOSBcdWFkMDBcdWI5YWNcdWM3NzhcdWM3NzQgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU0XHViOTc4IFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWM2MjVcdWMwYzEgXHVjODE1XHVjNmQwXHVjNzQwIGkrMSwgaSsyLCAuLi4uICwgTlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwXHViMzcwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM3MDRcdWNlNThcdWQ1NWMgXHViZTRjXHViNTI5XHViY2Y0XHViMmU0IFx1YjE5Mlx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHViZTRjXHViNTI5XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViZTRjXHViNTI5XHVjNzU4IFx1YzYyNVx1YzBjMVx1Yzc0MCBcdWJjZjRcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDgpIE49NiwgSCA9IHsxMCwgMywgNywgNCwgMTIsIDJ9XHVjNzc4IFx1YWNiZFx1YzZiMDxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgPSBcclxuID0gICAgICAgICAgID0gXHJcbiA9ICAgICAtICAgICA9IFxyXG4gPSAgICAgPSAgICAgPSAgICAgICAgLSZndDsgXHVhZDAwXHViOWFjXHVjNzc4XHVjNzc0IFx1YmNmNFx1YjI5NCBcdWJjMjlcdWQ1YTVcclxuID0gIC0gID0gID0gID0gICBcclxuID0gID0gID0gID0gID0gID0gXHJcbjEwICAzICA3ICA0ICAxMiAyICAgICAtJmd0OyBcdWJlNGNcdWI1MjlcdWM3NTggXHViMTkyXHVjNzc0XHJcblsxXVsyXVszXVs0XVs1XVs2XSAgICAtJmd0OyBcdWJlNGNcdWI1MjlcdWM3NTggXHViYzg4XHVkNjM4PFwvcHJlPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xXHViYzg4IFx1YWQwMFx1YjlhY1x1Yzc3OFx1Yzc0MCAyLCAzLCA0XHViYzg4IFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWM2MjVcdWMwYzFcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjJcdWJjODggXHVhZDAwXHViOWFjXHVjNzc4XHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjNjI1XHVjMGMxXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4zXHViYzg4IFx1YWQwMFx1YjlhY1x1Yzc3OFx1Yzc0MCA0XHViYzg4IFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWM2MjVcdWMwYzFcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjRcdWJjODggXHVhZDAwXHViOWFjXHVjNzc4XHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjNjI1XHVjMGMxXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2xpPlxyXG5cdDxsaT41XHViYzg4IFx1YWQwMFx1YjlhY1x1Yzc3OFx1Yzc0MCA2XHViYzg4IFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWM2MjVcdWMwYzFcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjZcdWJjODggXHVhZDAwXHViOWFjXHVjNzc4XHVjNzQwIFx1YjljOFx1YzljMFx1YjljOVx1Yzc3NFx1YmJjMFx1Yjg1YyBcdWIyZTRcdWI5NzggXHViZTRjXHViNTI5XHVjNzU4IFx1YzYyNVx1YzBjMVx1Yzc0NCBcdWQ2NTVcdWM3NzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWQwMFx1YjlhY1x1Yzc3OFx1YjRlNFx1Yzc3NCBcdWM2MjVcdWMwYzFcdWM4MTVcdWM2ZDBcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDFkIFx1YzIxOFx1YjI5NCAzICsgMCArIDEgKyAwICsgMSArIDAgPSA1XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJlNGNcdWI1MjlcdWM3NTgmbmJzcDtcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuKDEgJmxlOyBOICZsZTsgODAsMDAwKTxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNCBcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWFjMDEgXHViZTRjXHViNTI5XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBoPHN1Yj5pPFwvc3ViPiBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuICgxICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDAsMDAwKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5cdWFjMDEgXHVhZDAwXHViOWFjXHVjNzc4XHViNGU0XHVjNzc0IFx1YmNhNFx1Y2U1OFx1YjljOFx1ZDBiOVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViZTRjXHViNTI5XHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjE5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhZCBIYWlyIERheSIsImRlc2NyaXB0aW9uIjoiPHA+U29tZSBvZiBGYXJtZXIgSm9obiYjMzk7cyBOIGNvd3MgKDEgJmx0Oz0gTiAmbHQ7PSA4MCwwMDApIGFyZSBoYXZpbmcgYSBiYWQgaGFpciBkYXkhIFNpbmNlIGVhY2ggY293IGlzIHNlbGYtY29uc2Npb3VzIGFib3V0IGhlciBtZXNzeSBoYWlyc3R5bGUsIEZKIHdhbnRzIHRvIGNvdW50IHRoZSBudW1iZXIgb2Ygb3RoZXIgY293cyB0aGF0IGNhbiBzZWUgdGhlIHRvcCBvZiBvdGhlciBjb3dzJiMzOTsgaGVhZHMuPFwvcD5cclxuXHJcbjxwPkVhY2ggY293IGkgaGFzIGEgc3BlY2lmaWVkIGhlaWdodCBoW2ldICgxICZsdDs9IGhbaV0gJmx0Oz0gMSwwMDAsMDAwLDAwMCkgYW5kIGlzIHN0YW5kaW5nIGluIGEgbGluZSBvZiBjb3dzIGFsbCBmYWNpbmcgZWFzdCAodG8gdGhlIHJpZ2h0IGluIG91ciBkaWFncmFtcykuIFRoZXJlZm9yZSwgY293IGkgY2FuIHNlZSB0aGUgdG9wcyBvZiB0aGUgaGVhZHMgb2YgY293cyBpbiBmcm9udCBvZiBoZXIgKG5hbWVseSBjb3dzIGkrMSwgaSsyLCBhbmQgc28gb24pLCBmb3IgYXMgbG9uZyBhcyB0aGVzZSBjb3dzIGFyZSBzdHJpY3RseSBzaG9ydGVyIHRoYW4gY293IGkuPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoaXMgZXhhbXBsZTo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICA9XHJcbj0gICAgICAgPVxyXG49ICAgLSAgID0gICAgICAgICAgIENvd3MgZmFjaW5nIHJpZ2h0IC0tJmd0O1xyXG49ICAgPSAgID1cclxuPSAtID0gPSA9XHJcbj0gPSA9ID0gPSA9XHJcbjEgMiAzIDQgNSA2PFwvcHJlPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Db3cjMSBjYW4gc2VlIHRoZSBoYWlyc3R5bGUgb2YgY293cyAjMiwgMywgNDxcL2xpPlxyXG5cdDxsaT5Db3cjMiBjYW4gc2VlIG5vIGNvdyYjMzk7cyBoYWlyc3R5bGU8XC9saT5cclxuXHQ8bGk+Q293IzMgY2FuIHNlZSB0aGUgaGFpcnN0eWxlIG9mIGNvdyAjNDxcL2xpPlxyXG5cdDxsaT5Db3cjNCBjYW4gc2VlIG5vIGNvdyYjMzk7cyBoYWlyc3R5bGU8XC9saT5cclxuXHQ8bGk+Q293IzUgY2FuIHNlZSB0aGUgaGFpcnN0eWxlIG9mIGNvdyA2PFwvbGk+XHJcblx0PGxpPkNvdyM2IGNhbiBzZWUgbm8gY293cyBhdCBhbGwhPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+TGV0IGNbaV0gZGVub3RlIHRoZSBudW1iZXIgb2YgY293cyB3aG9zZSBoYWlyc3R5bGUgaXMgdmlzaWJsZSBmcm9tIGNvdyBpOyBwbGVhc2UgY29tcHV0ZSB0aGUgc3VtIG9mIGNbMV0gdGhyb3VnaCBjW05dLiBGb3IgdGhpcyBleGFtcGxlLCB0aGUgZGVzaXJlZCBpcyBhbnN3ZXIgMyArIDAgKyAxICsgMCArIDEgKyAwID0gNS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbnVtYmVyIG9mIGNvd3MsIE4uPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIHRoZSBoZWlnaHQgb2YgY293IGkuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgc3VtIG9mIGNbMV0gdGhyb3VnaCBjW05dLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO November 2006 Contest > Silver 1번