Elearning CodePath – CTP Online Judge

TỔNG CHỈ SỐ LỚN HƠN GẦN NHẤT

SUME

🟢 Medium #Stack

### 📌 Thông tin chung

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

Cho một mảng $A$ gồm $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($1 \le i \le n$). Với mỗi giá trị $a_i$, hãy tính giá trị $x + y$ trong đó:
- $x$ là chỉ số lớn nhất nhỏ hơn $i$ thỏa mãn $a_x > a_i$. Nếu không tồn tại $x$ thỏa mãn thì $x = -1$.
- $y$ là chỉ số nhỏ nhất lớn hơn $i$ thỏa mãn $a_y > a_i$. Nếu không tồn tại $y$ thỏa mãn thì $y = -1$.

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file văn bản SUME.INP gồm:
- Dòng đầu tiên, chứa số nguyên dương $N$ ($1 \le N \le 10^6$).
- Dòng tiếp theo chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$).

### 📤 Định dạng Đầu ra

Ghi ra file văn bản SUME.OUT ghi $n$ số nguyên, số thứ $i$ ghi kết quả của $a_i$.

### ✨ Ví dụ

| SUME.INP | SUME.OUT |
| :--- | :--- |
| 5 <br> 5 4 1 3 2 | -2 0 6 1 3 |

**Giải thích:**
- Với $i=1, a_1=5: x=-1, y=-1 \Rightarrow x+y = -2$.
- Với $i=2, a_2=4: x=1, y=-1 \Rightarrow x+y = 0$.
- Với $i=3, a_3=1: x=2, y=4 \Rightarrow x+y = 6$.
- Với $i=4, a_4=3: x=2, y=-1 \Rightarrow x+y = 1$.
- Với $i=5, a_5=2: x=4, y=-1 \Rightarrow x+y = 3$.

### 🏷 Subtasks

- Subtask 1 (30%): $N \le 10^3$.
- Subtask 2 (70%): $N \le 10^6$.

✅ Đã AC: 5 / 12 submissions