上界应为 $n-1+\max a_i$ .

考虑这一组 hack 数据：

1
1000000000000000000 1 0

很多题解的上界都是 $10^9$ ，会被叉掉。