toad 最近看太多三國，迷上了烽火台，因此 toad 決定要蓋一組從新竹到台北的烽火台。

從新竹到台北的道路上有 $N$ 座 toad 可以購買的地基，依序（從新竹到台北）編號為第 $1$ 座、第 $2$ 座、$\dots$ 、第 $N$ 座。為了要讓烽火台的傳訊順利，相鄰的兩座地基 toad 至少要購買一座，也就是對於第 $i$ 座與第 $i + 1$ 座地基，至少要有一座被 toad 購買。當然，因為 toad 很有錢，因此在滿足前面的要求下，他可以購買任意多的地基。

在所有合法的頻道 $[0, M - 1]$ 之中，toad 可以自己決定他發送的訊息的頻道 $x$。而對於第 $i$ 座地基，有一個頻率指數 $A_i$，如果 toad 選擇在頻道 $x$ 發送訊息，那麼該座地基蓋出的烽火台的發送品質就為 $(A_i + x) \text{ mod } M$ ，也就是 $A_i + x$ 除以 $M$ 的餘數。

toad 希望選擇最佳的頻道與購買的地基的組合，讓蓋出來的烽火台發送品質的 中位數 最大，可以請你幫助 toad 找到最佳的頻道與購買的地基的組合下，蓋出來的烽火台發送品質的中位數最大可以是多少嗎？

對於一個長度為 $n$ 的數列 $B$，我們定義 $B$ 的中位數為 $B$ 第 $\lceil \frac n 2 \rceil$ 小的元素，其中 $\lceil x \rceil$ 為不小於 $x$ 最小的整數。