Mở rộng cực trị

Với một mảng $b$ gồm các số nguyên dương, ta định nghĩa giá trị cực trị của $b$ là số lần ít nhất (có thể bằng $0$) cần thực hiện thao tác sau để mảng $b$ trở thành không giảm:

• Chọn một chỉ số $i$ với $1\le i\le |b|$ (trong đó $|b|$ là độ dài hiện tại của $b$).
• 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 mỗi thao tác, mảng $b$ dài thêm một phần tử và thao tác tiếp theo được thực hiện trên mảng vừa thay đổi. Có thể chứng minh mọi mảng số nguyên dương đều có thể biến thành không giảm bằng cách này.

Ví dụ, nếu $b=[2,4,3]$ và chọn chỉ số $2$, thao tác có thể tạo ra $[2,1,3,3]$, $[2,2,2,3]$ hoặc $[2,3,1,3]$. Với mảng này, một thao tác là đủ: $[2,4,3]\to [2,2,2,3]$, nên giá trị cực trị của nó bằng $1$.

Cho một mảng $a$ gồm $n$ số nguyên. Hãy tính tổng giá trị cực trị của tất cả các mảng con liên tiếp không rỗng của $a$, lấy dư cho $998244353$. Nếu một mảng con xuất hiện nhiều lần trong $a$, giá trị cực trị của nó được tính đúng số lần xuất hiện.

Một mảng $d$ là mảng con liên tiếp của $c$ nếu $d$ nhận được từ $c$ bằng cách xóa một số (có thể là $0$ hoặc tất cả) phần tử ở đầu và một số phần tử ở cuối.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le 10000$) là số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ ($1\le n\le {10}^5$).
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^5$).

Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là tổng giá trị cực trị của tất cả các mảng con liên tiếp của $a$, lấy dư cho $998244353$.

Ràng buộc

• $1\le t\le 10000$
• $1\le n\le {10}^5$
• $1\le a_i\le {10}^5$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ