Cheow – một sinh vật nhỏ tinh nghịch – vô tình bay vào một hành lang dài chứa đầy các vật cản: đá nhọn (mọc lên từ dưới đất) và đá nhô (thòng xuống từ trần hang). Các vật cản được sắp xếp luân phiên, bắt đầu từ đá nhọn, rồi tới đá nhô, rồi lại đá nhọn...

Hành lang có độ dài ~N~ đơn vị (với ~N~ là số chẵn) và chiều cao là ~H~ đơn vị.

Cheow không thể lách qua các chướng ngại vật. Thay vào đó, nó sẽ chọn một độ cao duy nhất và bay từ đầu đến cuối hành lang ở đúng độ cao đó, phá vỡ tất cả các chướng ngại vật chạm vào đường bay của mình.

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

Nhiệm vụ của bạn là giúp Cheow chọn độ cao sao cho:

• Số lượng chướng ngại vật bị phá là ít nhất.
• Đếm xem có bao nhiêu cách chọn độ cao khác nhau đạt được số chướng ngại vật bị phá ít nhất đó.

Input

• Dòng đầu gồm hai số nguyên dương ~N~ ~(2 ≤ N ≤ 2×10^{5})~ và ~H~ ~(1 ≤ H ≤ 5×10^{5})~ -Là độ dài và chiều cao hành lang.
• Dòng thứ hai gồm ~N~ số nguyên dương ~h_1, h_2,..., h_N~: chiều cao của từng chướng ngại vật theo thứ tự từ trái sang phải, bắt đầu từ đá nhọn, rồi đá nhô, rồi lại đá nhọn, v.v...

Output

• In ra hai số nguyên: số chướng ngại vật ít nhất mà Cheow cần phá, và số cách chọn độ cao khác nhau để đạt được kết quả đó.

📌 Example

Input

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

Output

7 2

💡 Explanation

Cheow thử bay ở các độ cao từ 1 đến 5:

• Với độ cao 1 → phá 7 vật cản.
• Với độ cao 2 → phá 8 vật cản.
• ...
• Với độ cao 5 → phá 7 vật cản (ít nhất). → Có 2 cách chọn độ cao đạt kết quả này (ở độ cao 1 và 5 chẳng hạn).