回答編集履歴

  1000000000000000000

  ```

  期待する答えは `1000000000000000002`になるはずですが、実行結果は `999999999999999999` になります。

  A,Nともに取りうる値は10^18までですが、数列Aの最大数が10^6あるため、答えとなりうる値が最大で10^10+10^6あることになります。このプログラムでは答えとして取りうる値の最大値をright側に入れて開始していますが、最大値が実際に取りうる最大値に足りていないので答えとして10^18以上の数値が来た場合にこれ以上の数が探索できずにleftにひたすらmidが加算されていきます。最終的にright未満の数値である10^18-1までしかleftが増加しません。

 

  なので、対策としてはrightの初期値をもう少し増やしてあげれば良い、ということになります。最低10^18 + 10^6 + 1 あれば大丈夫だと思いますが、それより大きい値でも2倍程度なら処理速度に大差ありません。10^18*2くらいで開始すれば問題なくACが取れると思います。