Solution:
Because we can change at most n numbers. And the new value at most can be $2\cdot 10^9$.
So, we replace all the number to two big prime numbers (except the minimum value): $10^9+7$ and $10^9+9$.
Code:
C++:
Submission #115908484 - Codeforces
Codeforces. Programming competitions and contests, programming community
java:
Submission #115621893 - Codeforces
Codeforces. Programming competitions and contests, programming community
