Giải bài trực tuyến

Matija muốn sơn lại hàng rào nhà mình. Hàng rào của anh ấy được ghép bởi N tấm ván liên tiếp, mỗi tấm rộng 1 cm và có chiều cao khác nhau. Để sơn nhanh chóng và dễ dàng hơn, anh ấy đã mua "Super Pain Roller Deluxe" (một cây lăn xịn). Cây lăn có chiều rộng x cm. Mỗi lần dùng, anh ấy phải để cây lăn chạm vào bức tường hoàn toàn, nếu không sẽ không sơn được gì cả. Mặt khác, lúc nào cũng phải để cho cây lăn song song với mặt đất. Nói cách khác, anh ấy sẽ chọn ra x tấm ván liên tiếp và sơn từ dưới lên đến độ cao của tấm ván thấp nhất trong x tấm ván đó.

Tuy nhiên, cây lăn không thể giúp Matija sơn hết được hàng rào. Phần diện tích còn lại không thể sơn bằng cây lăn, anh ấy sẽ sơn bằng cọ nhỏ. Hãy giúp anh ấy tính xem phần diện tích phải sơn bằng cọ nhỏ nhất có thể là bao nhiêu, và số lần dùng cây lăn ít nhất để đạt được điều đó.

Input

• Dòng đầu ghi số nguyên N (1 ≤ N ≤ 10⁶) là số tấm ván cần phải sơn và số nguyên X (1 ≤ X ≤ 10⁵).
• Dòng tiếp theo ghi N số nguyên dương (mỗi số không quá 10⁶) mô tả chiều cao của từng tấm ván.

Output

• Dòng thứ nhất ghi diện tích nhỏ nhất phải sơn bằng cọ.
• Dòng thứ hai ghi số lần dùng cây lăn ít nhất để đạt được diện tích đó.

Example

Input:
5 3
5 3 4 4 5

Output:
3
2