Đô thị hoá
View as PDFNhân dịp nghỉ hè, Tèo được dẫn đi du lịch ở một đất nước rất hưng thịnh mang tên Vương quốc Cổ Lùn do một vị hoàng đế tài ba đang cai trị. Vương quốc Cổ Lùn có ~n~ thành phố được đánh số từ 1 đến ~n~. Trong những năm qua, Vương quốc Cổ Lùn đã có một tốc độ đô thị hoá đột biến với vô số các khu đô thị và đặc khu kinh tế được xây dựng và phát triển rất mạnh mẽ. Theo sau đó là sự sinh sôi nảy nở của các thành phố lớn với các toà nhà chọc trời. Tại những nơi đây, cư dân thành phố được tiếp cận với các dịch vụ sang trọng và sử dụng các sản phẩm xa xỉ bậc nhất thế giới. Vì thế, Tèo rất hào hứng khi được đặt chân đến nơi đây.
Tèo được dẫn đến gặp đức vua của vương quốc. Không như tưởng tượng của Tèo, vị vua của vương quốc mang dáng vẻ khá xanh xao và mệt mỏi. Mấy ngày gần đây, ngài mất ăn mất ngủ vì tình hình kinh tế của vương quốc. Hiện nay, Vương quốc Cổ Lùn trông có vẻ phát triển rất thịnh vượng nhưng lại đang phải đối mặt với một vấn đề kinh tế rất nghiêm trọng. Thực ra, do những vùng đặc khu kinh tế phát triển quá mạnh mẽ khiến cho những nơi khác không bắt kịp, điều kiện đời sống giảm dần và trở thành những khu ổ chuột. Thấy thế, Tèo quyết tâm giúp đỡ nhà vua một tay. Cậu sẽ chọn ra những vùng có điều kiện sống kém nhất và kêu đức vua đẩy mạnh tài trợ đến những vùng này, giúp những nơi đó phát triển. Cậu gọi chỉ số đô thị hoá của thành phố ~i~ là ~a_i~. Và chỉ số đô thị hoá của một vùng các thành phố liên tiếp từ ~i~ đến ~j~ ~(i \leq j)~ là trung bình cộng chỉ số đô thị hoá của các thành phố từ ~i~ đến ~j~ (tức là ~\frac{a_i+a_{i+1}+a_{i+2}+...+a_j}{j - i + 1}~).
Tèo sẽ chọn ra những vùng các thành phố liên tiếp có chỉ số đô thị hoá nhỏ nhất và báo cáo lại với nhà vua. Nếu có nhiều vùng cùng có chỉ số đô thị hoá nhỏ nhất thì cậu sẽ chọn những vùng có số thành phố là lớn nhất. Sau khi chọn được những vùng thoả điều kiện, Tèo sẽ báo cáo lên nhà vua và chọn chỉ số đại diện cho mỗi vùng là số thứ tự nhỏ nhất của các thành phố có trong vùng. Ví dụ như một vùng gồm các thành phố từ ~i~ đến ~j~ ~(i \leq j)~ sẽ có chỉ số đại diện là ~i~. Các vùng sẽ được báo cáo theo thứ tự tăng dần của chỉ số đại diện. Nhưng cậu chợt nhận ra cậu không biết phải làm sao bởi vì vương quốc này quá đỗi rộng lớn với số thành phố có thể lên đến ~10^7~. Nhưng Tèo biết người thông minh như bạn chắc chắn sẽ biết cách giải quyết vấn đề này!!!
Input
- Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \leq 10^7)~ là số thành phố trong Vương quốc Cổ Lùn.
- Dòng tiếp theo chứa dãy số nguyên dương ~a_1,a_2,a_3,...,a_n~ lần lượt là chỉ số đô thị hoá của n thành phố.
Output
Gồm 3 dòng
- Dòng đầu chứa ~val~ là giá trị đô thị hoá nhỏ nhất của các vùng thành phố liên tiếp.
- Dòng tiếp theo chứa ~num~ là số thành phố lớn nhất có trong vùng.
- Dòng cuối cùng chứa những chỉ số đại diện của các vùng thành phố liên tiếp thoả điều kiện.
Sample Input
9
1 1 1 2 2 2 3 3 3
Sample Output
1
3
1
Explaination
Trong test ví dụ, ta thấy chỉ số đô thị hoá của các vùng thành phố liên tiếp ~val~ nhỏ nhất bằng ~1~. Đồng thời trong tất cả các vùng thành phố có chỉ số đô thị hoá bằng ~1~, vùng gồm 3 thành phố đầu tiên ~a_1,a_2,a_3~ là vùng có nhiều thành phố nhất. Vùng này có chỉ số đại diện là ~1~.
Subtasks
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~10 \%~ | ~n \leq 100~ |
| ~2~ | ~40 \%~ | ~n \leq 10^3~ |
| ~3~ | ~50 \%~ | Không có ràng buộc gì thêm |
Comments
hi
moij
Sai chính tả r. Phải là moji 😒