시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 730 255 182 39.825%

문제

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+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmU0Y1x1YjUyOVx1Yzc1OCZuYnNwO1x1YWMxY1x1YzIxOCBOXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4oMSAmbGU7IE4gJmxlOyA4MCwwMDApPFwvbGk+XHJcblx0PGxpPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0IFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YWMwMSBcdWJlNGNcdWI1MjlcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIGg8c3ViPmk8XC9zdWI+IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gKDEgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCwwMDApPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPlx1YWMwMSBcdWFkMDBcdWI5YWNcdWM3NzhcdWI0ZTRcdWM3NzQgXHViY2E0XHVjZTU4XHViOWM4XHVkMGI5XHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJlNGNcdWI1MjlcdWM3NTggXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MTk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFkIEhhaXIgRGF5IiwiZGVzY3JpcHRpb24iOiI8cD5Tb21lIG9mIEZhcm1lciBKb2huJiMzOTtzIE4gY293cyAoMSAmbHQ7PSBOICZsdDs9IDgwLDAwMCkgYXJlIGhhdmluZyBhIGJhZCBoYWlyIGRheSEgU2luY2UgZWFjaCBjb3cgaXMgc2VsZi1jb25zY2lvdXMgYWJvdXQgaGVyIG1lc3N5IGhhaXJzdHlsZSwgRkogd2FudHMgdG8gY291bnQgdGhlIG51bWJlciBvZiBvdGhlciBjb3dzIHRoYXQgY2FuIHNlZSB0aGUgdG9wIG9mIG90aGVyIGNvd3MmIzM5OyBoZWFkcy48XC9wPlxyXG5cclxuPHA+RWFjaCBjb3cgaSBoYXMgYSBzcGVjaWZpZWQgaGVpZ2h0IGhbaV0gKDEgJmx0Oz0gaFtpXSAmbHQ7PSAxLDAwMCwwMDAsMDAwKSBhbmQgaXMgc3RhbmRpbmcgaW4gYSBsaW5lIG9mIGNvd3MgYWxsIGZhY2luZyBlYXN0ICh0byB0aGUgcmlnaHQgaW4gb3VyIGRpYWdyYW1zKS4gVGhlcmVmb3JlLCBjb3cgaSBjYW4gc2VlIHRoZSB0b3BzIG9mIHRoZSBoZWFkcyBvZiBjb3dzIGluIGZyb250IG9mIGhlciAobmFtZWx5IGNvd3MgaSsxLCBpKzIsIGFuZCBzbyBvbiksIGZvciBhcyBsb25nIGFzIHRoZXNlIGNvd3MgYXJlIHN0cmljdGx5IHNob3J0ZXIgdGhhbiBjb3cgaS48XC9wPlxyXG5cclxuPHA+Q29uc2lkZXIgdGhpcyBleGFtcGxlOjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgID1cclxuPSAgICAgICA9XHJcbj0gICAtICAgPSAgICAgICAgICAgQ293cyBmYWNpbmcgcmlnaHQgLS0mZ3Q7XHJcbj0gICA9ICAgPVxyXG49IC0gPSA9ID1cclxuPSA9ID0gPSA9ID1cclxuMSAyIDMgNCA1IDY8XC9wcmU+XHJcblxyXG48dWw+XHJcblx0PGxpPkNvdyMxIGNhbiBzZWUgdGhlIGhhaXJzdHlsZSBvZiBjb3dzICMyLCAzLCA0PFwvbGk+XHJcblx0PGxpPkNvdyMyIGNhbiBzZWUgbm8gY293JiMzOTtzIGhhaXJzdHlsZTxcL2xpPlxyXG5cdDxsaT5Db3cjMyBjYW4gc2VlIHRoZSBoYWlyc3R5bGUgb2YgY293ICM0PFwvbGk+XHJcblx0PGxpPkNvdyM0IGNhbiBzZWUgbm8gY293JiMzOTtzIGhhaXJzdHlsZTxcL2xpPlxyXG5cdDxsaT5Db3cjNSBjYW4gc2VlIHRoZSBoYWlyc3R5bGUgb2YgY293IDY8XC9saT5cclxuXHQ8bGk+Q293IzYgY2FuIHNlZSBubyBjb3dzIGF0IGFsbCE8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5MZXQgY1tpXSBkZW5vdGUgdGhlIG51bWJlciBvZiBjb3dzIHdob3NlIGhhaXJzdHlsZSBpcyB2aXNpYmxlIGZyb20gY293IGk7IHBsZWFzZSBjb21wdXRlIHRoZSBzdW0gb2YgY1sxXSB0aHJvdWdoIGNbTl0uIEZvciB0aGlzIGV4YW1wbGUsIHRoZSBkZXNpcmVkIGlzIGFuc3dlciAzICsgMCArIDEgKyAwICsgMSArIDAgPSA1LjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBudW1iZXIgb2YgY293cywgTi48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIGhlaWdodCBvZiBjb3cgaS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIHRoZSBzdW0gb2YgY1sxXSB0aHJvdWdoIGNbTl0uPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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