#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template < class T> struct cLtraits_identity{
using type = T;
}
;
template < class T> using cLtraits_try_make_signed =
typename conditional<
is_integral< T> :: value ,
make_signed< T> ,
cLtraits_identity< T>
> :: type ;
template < class S, class T> struct cLtraits_common_type{
using tS = typename cLtraits_try_make_signed< S> :: type ;
using tT = typename cLtraits_try_make_signed< T> :: type ;
using type = typename common_type< tS,tT> :: type ;
}
;
template < class S, class T> inline auto min_L( S a, T b)
- > typename cLtraits_common_type< S,T> :: type {
return ( typename cLtraits_common_type< S,T> :: type ) a <= ( typename cLtraits_common_type< S,T> :: type ) b ? a : b;
}
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
class Solution{
public :
long long maxRunTime( int N, vector< int > & E) {
int M = E.size ( ) ;
long long Nzj9Y0kE;
long long bkxOPzPX;
long long WKqLrJHZ;
Nzj9Y0kE = 0 ;
bkxOPzPX = 1000000000000000LL;
while ( Nzj9Y0kE < bkxOPzPX) {
if ( ( Nzj9Y0kE + bkxOPzPX) % 2 == 0 ) {
WKqLrJHZ = ( Nzj9Y0kE + bkxOPzPX) / 2 ;
}
else {
WKqLrJHZ = ( Nzj9Y0kE + bkxOPzPX + 1 ) / 2 ;
}
int bs24PFPc;
long long R5MtCiij;
int YGwFZBGH = 0 ;
if ( ( 0 ) > ( ( M) - 1 ) ) {
R5MtCiij = 0 ;
}
else {
for ( bs24PFPc = 0 ; bs24PFPc <= ( M) - 1 ; bs24PFPc++ ) {
if ( YGwFZBGH == 0 ) {
R5MtCiij = min_L( WKqLrJHZ, E[ bs24PFPc] ) ;
YGwFZBGH = 1 ;
continue ;
}
R5MtCiij + = min_L( WKqLrJHZ, E[ bs24PFPc] ) ;
}
if ( YGwFZBGH== 0 ) {
R5MtCiij = 0 ;
}
}
if ( R5MtCiij/ N >= WKqLrJHZ) {
Nzj9Y0kE = WKqLrJHZ;
}
else {
bkxOPzPX = WKqLrJHZ - 1 ;
}
}
return bkxOPzPX;
}
}
;
// cLay version 20220116-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// class Solution {
// public:
// ll maxRunTime(int N, VI& E){
// int M = E.size();
// return bsearch_max[ll,x,0,1d15](sum[ll][i,0,M](min(x,E[i])) / N >= x);
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoInVucm9sbC1sb29wcyIpCiNwcmFnbWEgR0NDIG9wdGltaXplKCJpbmxpbmUiKQojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0ZW1wbGF0ZTxjbGFzcyBUPiBzdHJ1Y3QgY0x0cmFpdHNfaWRlbnRpdHl7CiAgdXNpbmcgdHlwZSA9IFQ7Cn0KOwp0ZW1wbGF0ZTxjbGFzcyBUPiB1c2luZyBjTHRyYWl0c190cnlfbWFrZV9zaWduZWQgPQogIHR5cGVuYW1lIGNvbmRpdGlvbmFsPAogICAgaXNfaW50ZWdyYWw8VD46OnZhbHVlLAogICAgbWFrZV9zaWduZWQ8VD4sCiAgICBjTHRyYWl0c19pZGVudGl0eTxUPgogICAgPjo6dHlwZTsKdGVtcGxhdGUgPGNsYXNzIFMsIGNsYXNzIFQ+IHN0cnVjdCBjTHRyYWl0c19jb21tb25fdHlwZXsKICB1c2luZyB0UyA9IHR5cGVuYW1lIGNMdHJhaXRzX3RyeV9tYWtlX3NpZ25lZDxTPjo6dHlwZTsKICB1c2luZyB0VCA9IHR5cGVuYW1lIGNMdHJhaXRzX3RyeV9tYWtlX3NpZ25lZDxUPjo6dHlwZTsKICB1c2luZyB0eXBlID0gdHlwZW5hbWUgY29tbW9uX3R5cGU8dFMsdFQ+Ojp0eXBlOwp9CjsKdGVtcGxhdGU8Y2xhc3MgUywgY2xhc3MgVD4gaW5saW5lIGF1dG8gbWluX0woUyBhLCBUIGIpCi0+IHR5cGVuYW1lIGNMdHJhaXRzX2NvbW1vbl90eXBlPFMsVD46OnR5cGV7CiAgcmV0dXJuICh0eXBlbmFtZSBjTHRyYWl0c19jb21tb25fdHlwZTxTLFQ+Ojp0eXBlKSBhIDw9ICh0eXBlbmFtZSBjTHRyYWl0c19jb21tb25fdHlwZTxTLFQ+Ojp0eXBlKSBiID8gYSA6IGI7Cn0KI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICByZXR1cm4gMDsKfQojdW5kZWYgbWFpbgpjbGFzcyBTb2x1dGlvbnsKICBwdWJsaWM6CiAgbG9uZyBsb25nIG1heFJ1blRpbWUoaW50IE4sIHZlY3RvcjxpbnQ+JiBFKXsKICAgIGludCBNID0gRS5zaXplKCk7CiAgICBsb25nIGxvbmcgTnpqOVkwa0U7CiAgICBsb25nIGxvbmcgYmt4T1B6UFg7CiAgICBsb25nIGxvbmcgV0txTHJKSFo7CiAgICBOemo5WTBrRSA9IDA7CiAgICBia3hPUHpQWCA9IDEwMDAwMDAwMDAwMDAwMDBMTDsKICAgIHdoaWxlKE56ajlZMGtFIDwgYmt4T1B6UFgpewogICAgICBpZigoTnpqOVkwa0UgKyBia3hPUHpQWCklMj09MCl7CiAgICAgICAgV0txTHJKSFogPSAoTnpqOVkwa0UgKyBia3hPUHpQWCkgLyAyOwogICAgICB9CiAgICAgIGVsc2V7CiAgICAgICAgV0txTHJKSFogPSAoTnpqOVkwa0UgKyBia3hPUHpQWCArIDEpIC8gMjsKICAgICAgfQogICAgICBpbnQgYnMyNFBGUGM7CiAgICAgIGxvbmcgbG9uZyBSNU10Q2lpajsKICAgICAgaW50IFlHd0ZaQkdIID0gMDsKICAgICAgaWYoKDApID4gKChNKS0xKSl7CiAgICAgICAgUjVNdENpaWogPSAwOwogICAgICB9CiAgICAgIGVsc2V7CiAgICAgICAgZm9yKGJzMjRQRlBjID0gMDsgYnMyNFBGUGMgPD0gKE0pLTE7IGJzMjRQRlBjKyspewogICAgICAgICAgaWYoWUd3RlpCR0ggPT0gMCl7CiAgICAgICAgICAgIFI1TXRDaWlqID1taW5fTChXS3FMckpIWiwgRVticzI0UEZQY10pOwogICAgICAgICAgICBZR3dGWkJHSCA9IDE7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgfQogICAgICAgICAgUjVNdENpaWogKz1taW5fTChXS3FMckpIWiwgRVticzI0UEZQY10pOwogICAgICAgIH0KICAgICAgICBpZihZR3dGWkJHSD09MCl7CiAgICAgICAgICBSNU10Q2lpaiA9IDA7CiAgICAgICAgfQogICAgICB9CiAgICAgIGlmKFI1TXRDaWlqLyBOID49IFdLcUxySkhaKXsKICAgICAgICBOemo5WTBrRSA9IFdLcUxySkhaOwogICAgICB9CiAgICAgIGVsc2V7CiAgICAgICAgYmt4T1B6UFggPSBXS3FMckpIWiAtIDE7CiAgICAgIH0KICAgIH0KICAgIHJldHVybiBia3hPUHpQWDsKICB9Cn0KOwovLyBjTGF5IHZlcnNpb24gMjAyMjAxMTYtMQoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIHt9Ci8vICN1bmRlZiBtYWluCi8vIAovLyBjbGFzcyBTb2x1dGlvbiB7Ci8vIHB1YmxpYzoKLy8gICBsbCBtYXhSdW5UaW1lKGludCBOLCBWSSYgRSl7Ci8vICAgICBpbnQgTSA9IEUuc2l6ZSgpOwovLyAgICAgcmV0dXJuIGJzZWFyY2hfbWF4W2xsLHgsMCwxZDE1XShzdW1bbGxdW2ksMCxNXShtaW4oeCxFW2ldKSkgLyBOID49IHgpOwovLyAgIH0KLy8gfTsK