int solve( vector< int > & height) {
int n = height.size ( ) ;
vector< int > leftMax( n) , rightMax( n) ;
for ( int i = 1 ; i < n; ++ i)
leftMax[ i] = max( height[ i- 1 ] , leftMax[ i- 1 ] ) ;
for ( int i = n- 2 ; i >= 0 ; -- i)
rightMax[ i] = max( height[ i+ 1 ] , rightMax[ i+ 1 ] ) ;
int ans = 0 ;
for ( int i = 0 ; i < n; ++ i) {
int waterLevel = min( leftMax[ i] , rightMax[ i] ) ;
if ( waterLevel >= height[ i] ) ans + = waterLevel - height[ i] ;
}
return ans;
}
aW50IHNvbHZlKHZlY3RvcjxpbnQ+JiBoZWlnaHQpIHsKICAgICAgICBpbnQgbiA9IGhlaWdodC5zaXplKCk7CiAgICAgICAgdmVjdG9yPGludD4gbGVmdE1heChuKSwgcmlnaHRNYXgobik7CiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPCBuOyArK2kpIAogICAgICAgICAgICBsZWZ0TWF4W2ldID0gbWF4KGhlaWdodFtpLTFdLCBsZWZ0TWF4W2ktMV0pOwogICAgICAgIGZvciAoaW50IGkgPSBuLTI7IGkgPj0gMDsgLS1pKSAKICAgICAgICAgICAgcmlnaHRNYXhbaV0gPSBtYXgoaGVpZ2h0W2krMV0sIHJpZ2h0TWF4W2krMV0pOwogICAgICAgIAogICAgICAgIGludCBhbnMgPSAwOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgICAgIGludCB3YXRlckxldmVsID0gbWluKGxlZnRNYXhbaV0sIHJpZ2h0TWF4W2ldKTsKICAgICAgICAgICAgaWYgKHdhdGVyTGV2ZWwgPj0gaGVpZ2h0W2ldKSBhbnMgKz0gd2F0ZXJMZXZlbCAtIGhlaWdodFtpXTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGFuczsKCQp9