Gửi bài giải
Điểm:
5,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Một dãy số x1, x2, ..., xm được gọi là dominative nếu tồn tại một giá trị k xuất hiện nhiều hơn m/2 lần. Ví dụ:
Dãy [3,2,2] là dominative vì giá trị xuất hiện 2 lần, lớn hơn 3/2
Dãy [1,2,3,2] không phải dominative vì không có giá trị nào xuất hiện nhiều hơn 4/2 = 2
Yêu cầu: Cho dãy a1, a2, ..., an, bạn cần đếm số cách chia dãy này thành các đoạn con liên tiếp sao cho mỗi đoạn con đều không dominative.
Đầu vào:
Dòng đầu tiên chứa số nguyên n (1 <= n <= 3000)
Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 <= ai <= 10^9)
Đầu ra:
In ra số cách chia thỏa mãn chia lấy dư cho 10^9 + 7
Input:
4
3 6 6 9
Output:
2
Ở test này, có 2 cách chia là [3,6,6,9] hoặc [3,6],[6,9]
Input:
6
1 2 1 2 1 2
Output:
4
Bình luận