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
![](https://codeforces.org/s/99452/images/codeforces-telegram-square.png)
java:
Submission #115621893 - Codeforces
Codeforces. Programming competitions and contests, programming community
![](https://codeforces.org/s/58467/images/codeforces-telegram-square.png)