Elearning CodePath – CTP Online Judge

Sức mạnh lớn nhất (MAXSTRONG)

291_SCMNH

🟢 Easy #General #Range Query #Monotonic Stack

## 💻 Đề Bài:

### 📌 **Thông tin chương trình**

---

### 📝 **Bài toán**

Trong giờ học bóng rổ, có $N$ học sinh đứng thành một hàng, được đánh số từ $1$ đến $N$ từ trái qua phải. Học sinh thứ $i$ có chiều cao $H_i$.

* Một dãy các học sinh **liên tiếp** tạo thành một nhóm.
* **Kích cỡ** của nhóm là số lượng các học sinh trong nhóm.
* **Sức mạnh** của nhóm được đo bằng chiều cao của học sinh **thấp nhất** trong nhóm (giá trị $\min(H_i)$).

Thầy giáo muốn biết, với mỗi kích cỡ nhóm $K$ ($1 \le K \le N$), thì **sức mạnh lớn nhất** của một nhóm học sinh với kích cỡ $K$ bằng bao nhiêu?

### 📥 **Định dạng Input**

* **Dòng 1:** Ghi số nguyên dương $N$ ($1 \le N \le 10^5$).
* **Dòng 2:** Ghi $N$ số nguyên dương $H_1, H_2, \dots, H_N$ ($1 \le H_i \le 10^9$) là chiều cao của các học sinh.

**Giới hạn:**
$$1 \le N \le 10^5$$
$$1 \le H_i \le 10^9$$

### 📤 **Định dạng Output**

In ra $N$ số nguyên trên một dòng, số thứ $K$ in ra sức mạnh lớn nhất của nhóm học sinh cỡ $K$. Ký hiệu $S_K$ là sức mạnh lớn nhất tìm được:
$$S_1, S_2, \dots, S_N$$

### ✨ **Ví dụ**

| Input (`MAXSTRONG.INP`) | Output (`MAXSTRONG.OUT`) |
| :--- | :--- |
| **10** | **6 4 4 3 3 2 2 1 1 1** |
| 1 2 3 4 5 4 3 2 1 6 | |

### 🔍 **Subtasks**

1.  **Subtask 1:** $N \le 100$. \[50%]
2.  **Subtask 2:** $N \le 10^5$. \[50%]

✅ Đã AC: 0 / 30 submissions