Bạn được trải nghiệm trò chơi Flappy Bird kỳ lạ, chú chim chỉ có thể di chuyển theo một đường thẳng từ vạch xuất phát đến vạch đích. Có tổng cộng ~n~ cột chắn, cột thứ ~i~ có chiều dài ~a_i~. Các cột được xây dựng hướng từ dưới lên trên và hướng từ trên xuống dưới xen kẽ nhau. Cột đầu tiên có hướng từ dưới lên trên. Bản đồ trò chơi được chia đều thành ~m~ dải theo chiều ngang. Hình dưới đây mô tả cho bản đồ trong ví dụ đầu tiên:

Vạch xuất phát ở ngoài cùng bên trái bản đồ, mục tiêu của bạn là đến được vạch đích ở ngoài cùng bên phải bản đồ. Bạn phải tiến hành chọn một trong ~m~ dải hàng ngang để điều khiển chú chim di chuyển theo đường thẳng. Hình dưới đây mô tả cách di chuyển của chú chim nếu chọn dải thứ ~4~ từ dưới lên trên:

Dễ dàng thấy rằng chú chim phải va chạm tổng cộng ~8~ cột chắn. Nếu chọn di chuyển ở dải thứ ~1~ hoặc thứ ~5~ từ dưới lên trên, chú chim chỉ va chạm với ~7~ cột chắn.

Nhiệm vụ của bạn hãy tìm cách di chuyển sao cho chú chim va chạm với ít cột chắn nhất có thể, đồng thời đếm số cách di chuyển như vậy.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(2 \le n,m \le 5 \times 10^6)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i < m)~.

Output

• In ra trên một dòng gồm hai số nguyên ~x~ và ~y~, trong đó ~x~ là số cột chắn ít nhất cần phải va chạm và ~y~ là số cách di chuyển tối ưu.

Examples

Sample Input 1

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

Sample Output 1

7 2

Sample Input 2

3 3
2 1 2

Sample Output 2

1 1

Scoring

• Subtask ~1~ ~-~ ~1000~ điểm: ~n,m \le 5 \times 10^3~
• Subtask ~2~ ~-~ ~750~ điểm: ~n,m \le 10^5~
• Subtask ~3~ ~-~ ~750~ điểm: Không có ràng buộc gì thêm