Một con tàu thăm dò vũ trụ sau một thời gian hoạt động, nay bị hỏng khi đáp xuống sao Hỏa, tàu đã phát tín hiệu cầu cứu về trái đất bằng một dãy các ký tự ở dạng mã nhị phân 0 và 1 liên tiếp nhau. Tuy nhiên, khi dữ liệu về trái đất nhận được bị sai lệch, một số ký tự 0 hoặc 1 bị chuyển thành các ký tự khác.

Yêu cầu

Cho một xâu ~s~ là tín hiệu được tàu thăm dò vũ trụ gửi từ sao Hỏa. Hãy cho biết cần phải thay thế bao nhiêu ký tự để xâu nhận được là dãy bao gồm các ký tự 0 và 1 liên tiếp.

Dữ liệu đầu vào

Gồm một xâu ~s~ có độ dài không quá ~10^5~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả bài toán.

Ví dụ

Ví dụ 1

INPUT

101121131104

OUTPUT

3

Giải thích: Cần phải thay thế ~3~ ký tự là 2, 3 và 4.

Ví dụ 2

INPUT

101105

OUTPUT

1

Giải thích: Cần phải thay thế ~1~ ký tự là 5.

Có ~N~ cây được trồng thành một hàng dọc trên con đường. Cây thứ ~i~ có chiều cao là ~a_i~. Để chỉnh trang đô thị, người ta muốn thay thế những cây có chiều cao thấp nhất bằng những cây mới. Nếu tất cả các cây có chiều cao bằng nhau thì không cần thay thế bằng cây mới.

Yêu cầu

Hãy tìm cây có chiều cao thấp nhất trước khi bị thay thế và số lượng cây không bị thay thế.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: Ghi số nguyên dương ~N~ là số lượng cây ~(2 \le N \le 10^6)~.
• Dòng 2: Ghi ~N~ số nguyên dương ~a_i~, là chiều cao của các cây ~(1 \le a_i \le 100)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là chiều cao của cây thấp nhất trước khi bị thay thế và số lượng cây không bị thay thế.

Ví dụ

Ví dụ 1

INPUT

8
3 5 4 7 2 2 4 7

OUTPUT

2 6

Ví dụ 2

INPUT

3
4 4 4

OUTPUT

4 3

Khi học về số nguyên tố, Tuệ Minh cảm thấy thích thú về tính chất của số này. Tuệ Minh mở rộng tính chất của số nguyên dương và đặt tên là số đặc biệt. Số đặc biệt là số có đúng ~3~ ước nguyên dương.

Yêu cầu

Với hai số nguyên dương ~A, B~ ~(1 \le A \le B)~ Tuệ Minh muốn biết có bao nhiêu số đặc biệt trong các số ~A, A + 1, A + 2, ..., B~.

Dữ liệu đầu vào

Gồm hai số nguyên dương ~A, B~.

Dữ liệu đầu ra

Gồm một số nguyên không âm duy nhất là số lượng số đặc biệt trong các số ~A, A + 1, A + 2, ..., B~.

Ràng buộc dữ liệu

• Subtask 1: 50% các test có ~A \le B \le 10^4~.
• Subtast 2: 25% các test có ~A \le B \le 10^6~.
• Subtast 3: 25% các test có ~A \le B \le 10^{12}~.

Ví dụ

Ví dụ 1

INPUT

1 6

OUTPUT

1

Giải thích: Trong các số nguyên dương từ ~1..6~ có ~1~ số đặc biệt là số ~4~.

Ví dụ 2

INPUT

3 125

OUTPUT

5

Giải thích: Trong các số nguyên dương từ ~3..125~ có ~5~ số đặc biệt là số ~4, 9, 25, 49, 121~.

Để đảm bảo phủ sóng tốt trên các vùng dân cư thưa thớt dọc trục lộ giao thông người ta đặt một số trạm phát sóng. Các trạm này được lắp trên sân nóc một số nhà nằm gần mặt đường. Điều kiện để đặt ~2~ trạm tiếp sóng liên tiếp nhau là giữa ~2~ tòa nhà đó không có một nhà nào cao hơn hoặc bằng một trong hai nơi đặt trạm.

Trục lộ giao thông khá thẳng nên các nhà trên mặt đường có thể coi như nằm trên một đường thẳng. Từ đầu đến cuối đường có ~n~ nhà, nhà thứ ~i~ có độ cao ~h_i~.

Yêu cầu

Hãy xác định số cặp nhà có thể đặt trạm phát sóng. Dĩ nhiên, hai nhà liên tiếp nhau luôn thỏa mãn điều kiện đặt trạm.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 2 \times 10^6)~.
• Dòng thứ hai chứa ~n~ số nguyên ~h_1, h_2, ..., h_n~ ~(1 \le h_i \le 10^6)~.

Dữ liệu đầu ra

Gồm một số nguyên là số cặp nhà có thể đặt trạm phát sóng.

Ràng buộc dữ liệu

• Subtask 1: 20% số test có ~n \le 100~.
• Subtask 2: 30% số test khác có ~n \le 5000~.
• Subtask 3: 50% số test còn lại có ~n \le 2 \times 10^6~.

Ví dụ

Ví dụ 1

INPUT

6
9 4 5 1 10 9

OUTPUT

8

Giải thích:

• Có ~6~ nhà nằm dọc theo trục lộ giao thông với độ cao lần lượt là: ~9, 4, 5, 1, 10, 9~.
• Có ~8~ cặp nhà có thể đặt trạm phát sóng là: ~(1, 2); (1, 3); (1, 5); (2, 3); (3, 4); (3, 5); (4, 5); (5, 6)~.

Một cửa hàng bày bán ~N~ bông hoa theo hàng ngang, bông hoa thứ ~i~ có giá trị ~F_i~ và chiều cao ~S_i~.

Yêu cầu

Bé Minh muốn mua một số bông hoa liên tiếp nhau để tạo thành bó hoa đẹp tặng mẹ, sao cho tổng giá trị các bông hoa ít nhất là ~M~, đồng thời bông hoa cao nhất là thấp nhất có thể. Bạn hãy giúp bé Minh nhé!

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu chứa hai số nguyên ~N~ và ~M~ ~(1 \le N \le 10^6;\ 1 \le M \le 10^{18})~ là số bông hoa trong cửa hàng và giá trị ít nhất của bó hoa mà bé Minh muốn mua.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~F_{i}, S_{i}~ là giá trị và chiều cao của bông hoa thứ ~i~ ~(1 \le F_{i}, S_{i} \le 10^9)~.

Dữ liệu cho trên cùng hàng cách nhau ít nhất một dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là chiều cao nhỏ nhất của bông hoa cao nhất trong các bông hoa mà bé Minh chọn mua. Dữ liệu đảm bảo bé Minh luôn chọn được bó hoa thỏa mãn điều kiện đề bài.

Ràng buộc dữ liệu

• Subtask 1: 30% số test đầu tiên có ~N \le 1000~.
• Subtask 2: 30% số test tiếp theo các giá trị ~S_i~ đã được sắp xếp tăng dần.
• Subtask 3: 40% số test cuối cùng không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5 10
4 10
6 15
3 5
4 9
3 6

OUTPUT

9

Giải thích: Bó hoa của bé Minh chọn mua gồm các bông hoa ~3, 4, 5~ có tổng giá trị là ~3 + 4 + 3 = 10~ và chiều cao lớn nhất của các bông hoa là ~max(5, 9, 6) = 9~.