This was my initial submission for the problem: https://codeforces.com/contest/1815/submission/237704790
However just changing the value of arr[0] to something a lot lesser, the code becomes accepted: https://codeforces.com/contest/1815/submission/237704230
The algorithm is pretty straightforward (as seen from my code) but why should the value of arr[0] be so less? isn't -(1e9 + 1) small enough for it? If you can help, perhaps by giving a test case which fails for the initial submission I will be grateful