Một con đom đóm bay vào một cái hang đầy những chướng ngại vật gồm: măng đá (nhô lên từ mặt đất) và nhũ đá (đâm xuống từ trần hang). Hang này dài ~N~ đơn vị (~N~ chẵn) và cao ~H~ đơn vị. Khi vào hang, vật cản đầu tiên là măng đá, sau đó là nhũ đã, rồi lại đến măng đá,...cứ thế thay phiên nhau.

Đây là một ví dụ về một hang dài ~14~ đơn vị và cao ~5~ đơn vị.

Con đom đóm này không phải là loài có thể bay quanh các chướng ngại vật. Thay vào đó, nó sẽ chọn một độ cao bắt đầu rồi bay từ đầu đến cuối hang, phá hết tất cả các chướng ngại vật trên đường bay của nó.

Theo ví dụ trên, nếu chọn mức ~4~, con đom đóm sẽ phá tất cả là ~8~ chướng ngại vật.

Đây không phải là lựa chọn tốt nhất vì con đom đóm sẽ ít mệt hơn nếu chọn mức ~1~ hoặc mức ~5~, lúc này nó chỉ cần phá ~7~ chướng ngại vật.

Bạn được cho chiều dài ~N~, chiều cao ~H~ và kích thước của tất cả các chướng ngại vật. Hãy xác định số chướng ngại vật tối thiểu mà con đom đóm cần phá để thoát khỏi hang, và có bao nhiêu cách chọn độ cao khác nhau đưa đến kết quả đó.

Input

• Dòng đầu gồm các số nguyên dương ~N \leq 2 \times 10^5~ và ~H \leq 5 \times 10^5~, là chiều dài và chiều cao của hang.
• Dòng thứ hai gồm ~N~ số nguyên dương ~h_1,h_2,\ldots,h_N~ là chiều cao các chướng ngại vật của hang. Lưu ý cách sắp xếp chướng ngại vật ở các hình vẽ trên.

Output

Gồm ~2~ số nguyên cách nhau là số chướng ngại vật ít nhất cần phá và số cách chọn khác nhau để có được kết quả đó.

Giới hạn

• Có ~30\%~ số test tương ứng với ~30\%~ số điểm có ~N \times H \leq 10^6~.
• ~70\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

6 7
1 5 3 3 5 1

Sample Output 1

2 3

Sample Input 2

14 5
1 3 4 2 2 4 3 4 3 3 3 2 3 3

Sample Output 2

7 2