Yêu cầu

Một hang động có N chướng ngại vật xếp dọc theo chiều dài và chiều cao hang là ~H~. Các chướng ngại vật gồm hai loại:

• Măng đá (mọc từ dưới lên),
• Nhũ đá (rơi từ trên xuống).

Chúng luân phiên xuất hiện dọc theo đường bay và chướng ngại vật đầu tiên luôn là măng đá, tiếp đến là nhũ đá, rồi lại măng đá, …

Một con đom đóm chọn một độ cao nguyên ~h~ (1 ≤ h ≤ H) và bay thẳng từ đầu đến cuối hang. Trên đường bay, mỗi khi gặp chướng ngại vật chắn ngang ở độ cao đó, nó phải phá hủy chướng ngại vật đó.

Hãy xác định:

• Số chướng ngại vật ít nhất mà đom đóm phải phá hủy khi chọn độ cao tối ưu, và
• Có bao nhiêu độ cao đạt được giá trị tối ưu đó.

Dữ liệu

Tệp BUBA.INP:

• Dòng 1: hai số nguyên ~N~, ~H~ (~2 ≤ N ≤ 200000~, ~2 ≤ H ≤ 500000~; ~N~ là số chẵn).

• Dòng 2…~N+1~: mỗi dòng là một số nguyên k — kích cỡ của chướng ngại vật ở vị trí tương ứng (các giá trị đều < H).

  • Các dòng lẻ (1, 3, 5, …) là măng đá (mọc từ dưới lên).
  • Các dòng chẵn (2, 4, 6, …) là nhũ đá (rơi từ trên xuống).

Kết quả

Tệp BUBA.OUT:

• Ghi hai số nguyên cách nhau một khoảng trắng:

  1. Số chướng ngại vật tối thiểu phải phá hủy;
  2. Số lượng độ cao ~h~ (~1 ≤ h ≤ H~) đạt được giá trị tối thiểu đó.

Ví dụ

Giới hạn dữ liệu

• ~2 ≤ N ≤ 200000~ (N chẵn), ~2 ≤ H ≤ 500000~.
• Mỗi kích cỡ chướng ngại vật là số nguyên dương < H.
• Các chướng ngại vật luân phiên: măng đá (dưới) rồi nhũ đá (trên), bắt đầu bằng măng đá.
• Yêu cầu tính toán hiệu quả (gợi ý: đếm tích luỹ/tiền tố – hậu tố để lấy số vật cản ở mỗi độ cao trong ~O(N + H)~).