#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
class Solution{
public :
int findBestValue( vector< int > & A, int T) {
int i;
int s = 0 ;
int c = 0 ;
int res;
int N = A.size ( ) ;
sort( A.begin ( ) , A.end ( ) ) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
s + = A[ i] ;
}
res = A[ N- 1 ] ;
for ( ;; ) {
while ( c < N && A[ N- 1 - c] == res) {
c++ ;
}
if ( abs ( s- T) < abs ( s- c- T) ) {
break ;
}
s - = c;
res-- ;
}
return res;
}
}
;
// cLay varsion 20200217-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// class Solution {
// public:
// int findBestValue(vector<int>& A, int T) {
// int s = 0, c = 0, res, N = A.size();
// sort(A.begin(), A.end());
// rep(i,N) s += A[i];
// res = A[N-1];
//
// for(;;){
// while(c < N && A[N-1-c] == res) c++;
// if(abs(s-T) < abs(s-c-T)) break;
// s -= c;
// res--;
// }
//
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgcmV0dXJuIDA7Cn0KI3VuZGVmIG1haW4KY2xhc3MgU29sdXRpb257CiAgcHVibGljOgogIGludCBmaW5kQmVzdFZhbHVlKHZlY3RvcjxpbnQ+JiBBLCBpbnQgVCl7CiAgICBpbnQgaTsKICAgIGludCBzID0gMDsKICAgIGludCBjID0gMDsKICAgIGludCByZXM7CiAgICBpbnQgTiA9IEEuc2l6ZSgpOwogICAgc29ydChBLmJlZ2luKCksIEEuZW5kKCkpOwogICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgIHMgKz0gQVtpXTsKICAgIH0KICAgIHJlcyA9IEFbTi0xXTsKICAgIGZvcig7Oyl7CiAgICAgIHdoaWxlKGMgPCBOICYmIEFbTi0xLWNdID09IHJlcyl7CiAgICAgICAgYysrOwogICAgICB9CiAgICAgIGlmKGFicyhzLVQpIDwgYWJzKHMtYy1UKSl7CiAgICAgICAgYnJlYWs7CiAgICAgIH0KICAgICAgcyAtPSBjOwogICAgICByZXMtLTsKICAgIH0KICAgIHJldHVybiByZXM7CiAgfQp9CjsKLy8gY0xheSB2YXJzaW9uIDIwMjAwMjE3LTEKCi8vIC0tLSBvcmlnaW5hbCBjb2RlIC0tLQovLyAjZGVmaW5lIG1haW4gZHVtbXlfbWFpbgovLyB7fQovLyAjdW5kZWYgbWFpbgovLyAKLy8gY2xhc3MgU29sdXRpb24gewovLyBwdWJsaWM6Ci8vICAgaW50IGZpbmRCZXN0VmFsdWUodmVjdG9yPGludD4mIEEsIGludCBUKSB7Ci8vICAgICBpbnQgcyA9IDAsIGMgPSAwLCByZXMsIE4gPSBBLnNpemUoKTsKLy8gICAgIHNvcnQoQS5iZWdpbigpLCBBLmVuZCgpKTsKLy8gICAgIHJlcChpLE4pIHMgKz0gQVtpXTsKLy8gICAgIHJlcyA9IEFbTi0xXTsKLy8gCi8vICAgICBmb3IoOzspewovLyAgICAgICB3aGlsZShjIDwgTiAmJiBBW04tMS1jXSA9PSByZXMpIGMrKzsKLy8gICAgICAgaWYoYWJzKHMtVCkgPCBhYnMocy1jLVQpKSBicmVhazsKLy8gICAgICAgcyAtPSBjOwovLyAgICAgICByZXMtLTsKLy8gICAgIH0KLy8gCi8vICAgICByZXR1cm4gcmVzOwovLyAgIH0KLy8gfTsK