Dưới mái hiên nhà cậu bé JOI sống ở Canada đã hình thành những cột băng rất đẹp. Nhân dịp này, JOI quyết định tìm hiểu về chúng.

Có \(N\) cột băng dưới mái hiên, nằm trên cùng một đường thẳng. Cột băng thứ \(i\) nằm ở vị trí cách đầu trái của mái hiên \(i\) cm (\(1\le i\le N\)), và ban đầu dài \(a_i\) cm, trong đó \(a_i\) là số nguyên dương. Các cột băng dài ra theo các quy tắc sau:

• Cột băng thứ \(i\) chỉ dài ra với tốc độ \(1\) cm mỗi giờ khi nó dài hơn cả cột băng thứ \(i-1\) lẫn cột băng thứ \(i+1\). Với hai cột băng ở hai đầu, chỉ xét cột băng bên cạnh duy nhất: cột thứ \(1\) dài ra nếu dài hơn cột thứ \(2\); cột thứ \(N\) dài ra nếu dài hơn cột thứ \(N-1\).
• Ngay khi đạt chiều dài \(L\) cm, một cột băng sẽ gãy ngay tại gốc. Từ đó trở đi, cột băng đã gãy được xem là có chiều dài \(0\) cm.

Ban đầu, mọi cặp cột băng kề nhau đều có chiều dài khác nhau. Với điều kiện này, sau đủ lâu, cả \(N\) cột băng đều sẽ gãy và có chiều dài \(0\) cm. JOI muốn biết cần bao lâu để đạt đến trạng thái đó.

Yêu cầu

Cho chiều dài ban đầu của \(N\) cột băng và chiều dài giới hạn \(L\), hãy viết chương trình tính thời gian cho đến khi tất cả các cột băng đều gãy.

Dữ liệu vào

Dữ liệu được cung cấp qua đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên \(N,L\), theo thứ tự này và cách nhau bởi dấu cách, lần lượt là số cột băng và chiều dài giới hạn của chúng.
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa số nguyên \(a_i\), là chiều dài ban đầu của cột băng thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chỉ chứa một số nguyên: thời gian tính bằng giờ cho đến khi tất cả các cột băng đều gãy.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
• \(2\le N\le100000=10^5\).
• \(2\le L\le50000\).
• \(1\le a_i<L\) (\(1\le i\le N\)).
• \(a_i\ne a_{i+1}\) (\(1\le i<N\)).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

Bài này có tổng cộng \(20\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm. Các tỷ lệ dưới đây được tính trên tổng điểm của bài.

• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le500\) và \(L\le1000\).

Ví dụ

4 6
4
2
3
5

8

6 10
3
4
1
9
5
1

15