시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 565 206 154 41.962%

문제

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+XHJcblxyXG48cD5cdWJlNGNcdWI1MjkgXHVhZDAwXHViOWFjXHVjNzc4XHViNGU0XHVjNzQwIFx1YjllNFx1YzZiMFx1YzEzMVx1YzJlNCBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWIyZTRcdWI5NzggXHViZTRjXHViNTI5XHVjNzU4IFx1YzYyNVx1YzBjMSBcdWM4MTVcdWM2ZDBcdWM3NDQgXHViYzM0XHVjZTU4XHViOWM4XHVkMGI5IFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmlcdWJjODhcdWM5ZjggXHViZTRjXHViNTI5XHVjNzU4IFx1ZDBhNFx1YWMwMCBoaVx1Yzc3NFx1YWNlMCwgXHViYWE4XHViNGUwIFx1YmU0Y1x1YjUyOVx1Yzc0MCBcdWM3N2NcdWI4MmNcdWI4NWMgXHVjMTFjIFx1Yzc4OFx1YWNlMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWNcdWI5Y2MgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmlcdWJjODhcdWM5ZjggXHViZTRjXHViNTI5IFx1YWQwMFx1YjlhY1x1Yzc3OFx1Yzc3NCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWI5NzggXHViZTRjXHViNTI5XHVjNzU4IFx1YzYyNVx1YzBjMSBcdWM4MTVcdWM2ZDBcdWM3NDAgaSsxLCBpKzIsIC4uLi4gLCBOXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZjBcdWIzNzAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWJlNGNcdWI1MjlcdWJjZjRcdWIyZTQgXHViMTkyXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWJlNGNcdWI1MjlcdWM3NzQgXHVjNzg4XHVjNzNjXHViYTc0IFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjNjI1XHVjMGMxXHVjNzQwIFx1YmNmNFx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOCkgTj02LCBIID0geyAxMCwgMywgNywgNCwgMTIsIDIgfVx1Yzc3OCBcdWFjYmRcdWM2YjA8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgID0gXHJcbiA9ICAgICAgICAgICA9IFxyXG4gPSAgICAgLSAgICAgPSBcclxuID0gICAgID0gICAgID0gICAgICAgIC0mZ3Q7IFx1YWQwMFx1YjlhY1x1Yzc3OFx1Yzc3NCBcdWJjZjRcdWIyOTQgXHViYzI5XHVkNWE1XHJcbiA9ICAtICA9ICA9ICA9ICAgXHJcbiA9ICA9ICA9ICA9ICA9ICA9IFxyXG4xMCAgMyAgNyAgNCAgMTIgMiAgICAgLSZndDsgXHViZTRjXHViNTI5XHVjNzU4IFx1YjE5Mlx1Yzc3NFxyXG5bMV1bMl1bM11bNF1bNV1bNl0gICAgLSZndDsgXHViZTRjXHViNTI5XHVjNzU4IFx1YmM4OFx1ZDYzODxcL3ByZT5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MVx1YmM4OCBcdWFkMDBcdWI5YWNcdWM3NzhcdWM3NDAgMiwgMywgNFx1YmM4OCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjNjI1XHVjMGMxXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4yXHViYzg4IFx1YWQwMFx1YjlhY1x1Yzc3OFx1Yzc0MCBcdWIyZTRcdWI5NzggXHViZTRjXHViNTI5XHVjNzU4IFx1YzYyNVx1YzBjMVx1Yzc0NCBcdWQ2NTVcdWM3NzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHQ8bGk+M1x1YmM4OCBcdWFkMDBcdWI5YWNcdWM3NzhcdWM3NDAgNFx1YmM4OCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjNjI1XHVjMGMxXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT40XHViYzg4IFx1YWQwMFx1YjlhY1x1Yzc3OFx1Yzc0MCBcdWIyZTRcdWI5NzggXHViZTRjXHViNTI5XHVjNzU4IFx1YzYyNVx1YzBjMVx1Yzc0NCBcdWQ2NTVcdWM3NzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHQ8bGk+NVx1YmM4OCBcdWFkMDBcdWI5YWNcdWM3NzhcdWM3NDAgNlx1YmM4OCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjNjI1XHVjMGMxXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT42XHViYzg4IFx1YWQwMFx1YjlhY1x1Yzc3OFx1Yzc0MCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3NzRcdWJiYzBcdWI4NWMgXHViMmU0XHViOTc4IFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWM2MjVcdWMwYzFcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViNTMwXHViNzdjXHVjMTFjLCBcdWFkMDBcdWI5YWNcdWM3NzhcdWI0ZTRcdWM3NzQgXHVjNjI1XHVjMGMxXHVjODE1XHVjNmQwXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2QxZCBcdWMyMThcdWIyOTQgMyArIDAgKyAxICsgMCArIDEgKyAwID0gNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJlNGNcdWI1MjlcdWM3NTgmbmJzcDtcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuKDEgJmxlOyBOICZsZTsgODAsMDAwKTxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNCBcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWFjMDEgXHViZTRjXHViNTI5XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBoPHN1Yj5pPFwvc3ViPiBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuICgxICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDAsMDAwKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5cdWFjMDEgXHVhZDAwXHViOWFjXHVjNzc4XHViNGU0XHVjNzc0IFx1YmMzNFx1Y2U1OFx1YjljOFx1ZDBiOVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViZTRjXHViNTI5XHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjE5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhZCBIYWlyIERheSIsImRlc2NyaXB0aW9uIjoiPHA+U29tZSBvZiBGYXJtZXIgSm9obiYjMzk7cyBOIGNvd3MgKDEgJmx0Oz0gTiAmbHQ7PSA4MCwwMDApIGFyZSBoYXZpbmcgYSBiYWQgaGFpciBkYXkhIFNpbmNlIGVhY2ggY293IGlzIHNlbGYtY29uc2Npb3VzIGFib3V0IGhlciBtZXNzeSBoYWlyc3R5bGUsIEZKIHdhbnRzIHRvIGNvdW50IHRoZSBudW1iZXIgb2Ygb3RoZXIgY293cyB0aGF0IGNhbiBzZWUgdGhlIHRvcCBvZiBvdGhlciBjb3dzJiMzOTsgaGVhZHMuPFwvcD5cclxuXHJcbjxwPkVhY2ggY293IGkgaGFzIGEgc3BlY2lmaWVkIGhlaWdodCBoW2ldICgxICZsdDs9IGhbaV0gJmx0Oz0gMSwwMDAsMDAwLDAwMCkgYW5kIGlzIHN0YW5kaW5nIGluIGEgbGluZSBvZiBjb3dzIGFsbCBmYWNpbmcgZWFzdCAodG8gdGhlIHJpZ2h0IGluIG91ciBkaWFncmFtcykuIFRoZXJlZm9yZSwgY293IGkgY2FuIHNlZSB0aGUgdG9wcyBvZiB0aGUgaGVhZHMgb2YgY293cyBpbiBmcm9udCBvZiBoZXIgKG5hbWVseSBjb3dzIGkrMSwgaSsyLCBhbmQgc28gb24pLCBmb3IgYXMgbG9uZyBhcyB0aGVzZSBjb3dzIGFyZSBzdHJpY3RseSBzaG9ydGVyIHRoYW4gY293IGkuPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoaXMgZXhhbXBsZTo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICA9XHJcbj0gICAgICAgPVxyXG49ICAgLSAgID0gICAgICAgICAgIENvd3MgZmFjaW5nIHJpZ2h0IC0tJmd0O1xyXG49ICAgPSAgID1cclxuPSAtID0gPSA9XHJcbj0gPSA9ID0gPSA9XHJcbjEgMiAzIDQgNSA2PFwvcHJlPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Db3cjMSBjYW4gc2VlIHRoZSBoYWlyc3R5bGUgb2YgY293cyAjMiwgMywgNDxcL2xpPlxyXG5cdDxsaT5Db3cjMiBjYW4gc2VlIG5vIGNvdyYjMzk7cyBoYWlyc3R5bGU8XC9saT5cclxuXHQ8bGk+Q293IzMgY2FuIHNlZSB0aGUgaGFpcnN0eWxlIG9mIGNvdyAjNDxcL2xpPlxyXG5cdDxsaT5Db3cjNCBjYW4gc2VlIG5vIGNvdyYjMzk7cyBoYWlyc3R5bGU8XC9saT5cclxuXHQ8bGk+Q293IzUgY2FuIHNlZSB0aGUgaGFpcnN0eWxlIG9mIGNvdyA2PFwvbGk+XHJcblx0PGxpPkNvdyM2IGNhbiBzZWUgbm8gY293cyBhdCBhbGwhPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+TGV0IGNbaV0gZGVub3RlIHRoZSBudW1iZXIgb2YgY293cyB3aG9zZSBoYWlyc3R5bGUgaXMgdmlzaWJsZSBmcm9tIGNvdyBpOyBwbGVhc2UgY29tcHV0ZSB0aGUgc3VtIG9mIGNbMV0gdGhyb3VnaCBjW05dLiBGb3IgdGhpcyBleGFtcGxlLCB0aGUgZGVzaXJlZCBpcyBhbnN3ZXIgMyArIDAgKyAxICsgMCArIDEgKyAwID0gNS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbnVtYmVyIG9mIGNvd3MsIE4uPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIHRoZSBoZWlnaHQgb2YgY293IGkuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgc3VtIG9mIGNbMV0gdGhyb3VnaCBjW05dLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 잘못된 번역을 찾은 사람: jh05013
  • 문제를 번역한 사람: skynet
  • 문제의 오타를 찾은 사람: twinparadox