Sau khi nhận được bức ảnh về chiếc kẹo mút từ Tiểu P, Tiểu W cảm thấy nó quá tuyệt vời, vì vậy cậu đã đáp lại bằng một dải ruy băng màu sắc không kém phần ấn tượng.
Tiểu W thêm các sắc thái sáng tối vào dải ruy băng để làm nó trở nên đẹp mắt hơn.
Đối với một dải ruy băng gồm $m$ ô, độ khó nhuộm $f(a)$ để tạo ra một chuỗi sáng tối $a$ có độ dài $m$ được định nghĩa như sau:
- Ban đầu, độ tối của mỗi ô trên dải ruy băng đều bằng $0$.
Bạn có thể thực hiện một số thao tác, mỗi thao tác bao gồm:
- Gấp dải ruy băng tại đường phân cách giữa hai ô bất kỳ. Thao tác gấp có thể thực hiện nhiều lần hoặc không gấp.
- Chọn một vị trí để nhỏ thuốc nhuộm đen. Thuốc nhuộm sẽ thấm từ trên xuống dưới, làm tăng độ tối của tất cả các ô trên đường đi của nó thêm $1$. Sau khi nhỏ thuốc, trải dải ruy băng ra.
$f(a)$ là số thao tác tối thiểu cần thiết để tất cả các vị trí có $a_i > 0$ đều có độ tối $\ge a_i$, và tất cả các vị trí có $a_i = 0$ đều có độ tối đúng bằng $0$.
Hiện tại, Tiểu W có một dải ruy băng độ dài $n$ và một chuỗi sáng tối dự kiến $b$ độ dài $n$. Cậu ấy vẫn chưa quyết định được cách phối màu nào là đẹp nhất, vì vậy cậu ấy muốn bạn tính tổng độ khó nhuộm của tất cả các dải ruy băng con có độ dài $r-l+1$ tương ứng với mọi đoạn con $[l, r]$ của $b$. Nói một cách hình thức, bạn cần tính $\sum\limits_{1\le l\le r\le n}f(b[l,r])$.
Kết quả cần được xuất ra dưới dạng modulo $2^{64}$.
Ví dụ
Dữ liệu vào 1
3 1 0 2
Dữ liệu ra 1
9
Dữ liệu vào 2
6 2 0 1 3 0 1
Dữ liệu ra 2
51
Dữ liệu vào 3
15 8 0 1 9 3 0 0 4 2 6 0 5 7 0 6
Dữ liệu ra 3
993
Giới hạn
| Số thứ tự test | Điểm | Giới hạn bổ sung |
|---|---|---|
| 1 | 5 | $b_i>0$ |
| 2 | 5 | $b_i>0$ |
| 3 | 5 | Số lượng $b_i>0$ không quá $300$ |
| 4 | 5 | Số lượng $b_i>0$ không quá $300$ |
| 5 | 5 | $n\leq15$ |
| 6 | 5 | $n\leq15$ |
| 7 | 5 | $n\leq500$ |
| 8 | 5 | $n\leq500$ |
| 9 | 5 | $n\leq500$ |
| 10 | 5 | $n\leq500$ |
| 11 | 5 | $n\leq5000$ |
| 12 | 5 | $n\leq5000$ |
| 13 | 5 | $n\leq5000$ |
| 14 | 5 | $n\leq5000$ |
| 15 | 5 | $n\leq50000$ |
| 16 | 5 | $n\leq50000$ |
| 17 | 5 | Không có |
| 18 | 5 | Không có |
| 19 | 5 | Không có |
| 20 | 5 | Không có |
Với tất cả các dữ liệu: $1 \le n\le 10^6, 0\le b_i \le 10 ^ 9$.