solution

Cho dãy $a$ gồm $n$ số. Với mỗi vị trí $i$, hãy đếm số đoạn liên tiếp (sub-array) mà phần tử cực đại bằng đúng $a_i$, sao cho mỗi đoạn được tính cho đúng một $i$ (tránh đếm trùng khi có giá trị lặp).

Gợi ý: với mỗi $i$, gọi $L$ = chỉ số gần nhất bên trái có $a_L > a_i$ (hoặc $-1$); $R$ = chỉ số gần nhất bên phải có $a_R \ge a_i$ (hoặc $n$). Số đoạn được tính là $(i - L)(R - i)$. Tổng các giá trị này luôn bằng $\binom{n+1}{2}$.

Ví dụ: $a = [3, 1, 4, 2]$ ⇒ $i=0\Rightarrow 2$, $i=1\Rightarrow 1$, $i=2\Rightarrow 6$, $i=3\Rightarrow 1$, tổng $10$.