Nới dãy
Xem dạng PDFVới một dãy ~b~ gồm các số nguyên dương, ta định nghĩa chi phí nới của ~b~ là số lần ít nhất phải thực hiện thao tác sau để dãy trở thành không giảm:
- Chọn một chỉ số ~i~ (~1 \le i \le |b|~, với ~|b|~ là độ dài hiện tại của dãy), rồi thay phần tử ~b_i~ bằng hai số nguyên dương ~x~ và ~y~ thỏa mãn ~x + y = b_i~. Sau thao tác, độ dài dãy tăng thêm 1 và thao tác kế tiếp thực hiện trên dãy mới.
Chẳng hạn với dãy ~b = \{2, 4, 3\}~, chọn ~i = 2~ có thể biến dãy thành ~\{2, 1, 3, 3\}~ hoặc ~\{2, 2, 2, 3\}~ hoặc ~\{2, 3, 1, 3\}~. Chỉ cần một thao tác ~\{2, 4, 3\} \to \{2, 2, 2, 3\}~ là dãy đã trở thành không giảm, nên chi phí nới của nó bằng 1. Có thể chứng minh mọi dãy số nguyên dương đều có thể làm cho không giảm theo cách này.
Cho dãy ~a~ gồm ~n~ số nguyên. Hãy tính tổng chi phí nới của tất cả các dãy con liên tiếp khác rỗng của ~a~, lấy theo mô-đun ~998244353~. Một dãy con liên tiếp là dãy thu được bằng cách bỏ đi một số phần tử ở đầu và ở cuối của dãy ban đầu; nếu một dãy con xuất hiện nhiều lần thì chi phí nới của nó được cộng đúng bằng số lần nó xuất hiện.
Input BAI3.INP
- Dòng đầu chứa số nguyên ~t~ (~1 \le t \le 10^4~) là số truy vấn cần trả lời.
- Mỗi truy vấn gồm hai dòng:
- Dòng đầu truy vấn chứa số nguyên ~n~ (~1 \le n \le 10^5~);
- Dòng thứ hai của truy vấn chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^5~).
Dữ liệu bảo đảm tổng của các ~n~ trên tất cả các truy vấn không vượt quá ~10^5~.
Output BAI3.OUT
Với mỗi truy vấn, in ra trên một dòng tổng chi phí nới của mọi dãy con liên tiếp, lấy theo mô-đun ~998244353~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 20% | ~n \le 80~ |
| 2 | 35% | ~n \le 5000~ |
| 3 | 45% | Không có ràng buộc bổ sung |
Sample Input 1
3
3
5 4 3
1
69
4
3 2 1 4
Sample Output 1
5
0
9
Notes
- Truy vấn thứ nhất, dãy ~\{5, 4, 3\}~:
- Chi phí nới của ~\{5, 4, 3\}~ là 3, của ~\{5, 4\}~ là 1, của ~\{4, 3\}~ là 1, còn ba dãy một phần tử đều có chi phí nới là 0;
- Tổng chi phí nới là ~3 + 1 + 1 + 0 + 0 + 0 = 5~.
- Truy vấn thứ hai: chỉ có một phần tử nên tổng chi phí nới bằng 0.
- Truy vấn thứ ba: tổng chi phí nới là 9.