Bỏ qua đến nội dung

CODER HUSC

Đăng nhập Đăng ký

Trang web này hoạt động tốt nhất khi JavaScript được cho phép.

Tổng giá trị nhỏ nhất

Mã bài: olpicpc003c01c Nhóm: Uncategorized Dạng bài: Undefined

Đăng nhập để nộp bài Xem dưới dạng PDF

Giới hạn thời gian: 3,0 s
Giới hạn bộ nhớ: 256 MB
Điểm: 0một phần
Tỉ lệ AC: 27,3%
Người giải: 19

Cho dãy hoán vị $A$ ~A~ với $N$ ~N~ phần tử. Hãy tính giá trị biểu thức sau:

$\displaystyle\sum_{l=1}^{N}\sum_{r=l}^{N}min(a_l,a_{l+1},...,a_r)$

Input

Dòng đầu tiên chứa số nguyên $N$ ~N~ ( $1 \le N \le 2.10^5$ ~1 \le N \le 2.10^5~).
Dòng thứ hai chứa các số nguyên $A_i$ ~A_i~ ( $1 \le A_i \le N$ ~1 \le A_i \le N~).
Dữ liệu đảm bảo rằng dãy số $A$ ~A~ là một dãy hoán vị hợp lệ.

Output

In ra một số nguyên là kết quả của biểu thức cần tính.

Examples

Input

3
2 1 3

Output

Scoring

Subtask $1$ ~1~ với $12\%$ ~12\%~ số điểm: $N \le 100$ ~N \le 100~
Subtask $2$ ~2~ với $28\%$ ~28\%~ số điểm: $N \le 2000$ ~N \le 2000~
Subtask $3$ ~3~ với $60\%$ ~60\%~ số điểm: $N \le 2.10^5$ ~N \le 2.10^5~

Bình luận

T-NAI-3217 Expert 08/07/2024 03:13

bửa thang

Điểm bình chọn: 0
iikarus Expert 29/06/2024 12:11

monotonic stack

Điểm bình chọn: -2

Bạn cần đăng nhập để viết bình luận, trả lời và bình chọn.

Đăng nhập để bình luận