Dự trữ nước

Một con mương cung cấp nước cho đồng ruộng. Để điều tiết dòng chảy, người dân đặt $n$ cột bê tông xếp cạnh nhau, có cùng độ rộng với con mương và có chiều cao lần lượt là $a_1,a_2,\dots ,a_n$. Khi trời mưa, nước sẽ đọng lại ở các cột có độ cao thấp hơn: phía trên cột thứ $i$, nước dâng tới mức thấp hơn trong hai độ cao: cột cao nhất trong các cột $1,2,\dots ,i$ và cột cao nhất trong các cột $i,i+1,\dots ,n$. Giả sử có $7$ cột với độ cao lần lượt là $4,1,3,2,5,1,6$ thì lượng nước mưa đọng lại là $10$ đơn vị.

Để mặt đáy được bằng phẳng, mọi người muốn nâng các cột bê tông lên. Cụ thể, cần chọn một độ cao nguyên $X$ lớn nhất và nâng các cột có độ cao thấp hơn $X$ lên bằng $X$ (các cột cao từ $X$ trở lên giữ nguyên) mà vẫn đảm bảo lượng nước mưa được giữ lại ít nhất là $M$ đơn vị.

Yêu cầu: Cho độ cao của các cột bê tông và lượng nước cần giữ lại, hãy tìm độ cao $X$ lớn nhất thỏa mãn yêu cầu. Giả sử lượng nước khi trời mưa là đủ để ngập các vũng nước và nước không bị thất thoát.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $M$.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên $X$ thỏa mãn yêu cầu. Trường hợp không có phương án (kể cả khi không nâng cột nào, lượng nước giữ lại vẫn ít hơn $M$) thì in ra $-1$.

Ràng buộc

• $1\le n\le {10}^5$.
• $1\le M\le {10}^{18}$.
• $1\le a_i\le 2·{10}^9$.

Ví dụ