Codeforces Round 752 (Div. 1) |
---|
Закончено |
Для массива $$$b$$$ из $$$n$$$ целых чисел определим экстремальное значение этого массива как минимальное количество раз (возможно, нулевое), которое необходимо выполнить следующую операцию, чтобы массив $$$b$$$ стал неубывающим:
Например, если $$$b = [2, 4, 3]$$$ и выбран индекс $$$2$$$, то возможными массивами после этой операции будут $$$[2, \underline{1}, \underline{3}, 3]$$$, $$$[2, \underline{2}, \underline{2}, 3]$$$, или $$$[2, \underline{3}, \underline{1}, 3]$$$. И, следовательно, для этого массива достаточно одной операции, чтобы он стал неубывающим: $$$[2, 4, 3] \rightarrow [2, \underline{2}, \underline{2}, 3]$$$.
Легко понять, что любой массив целых положительных чисел можно сделать неубывающим таким образом.
У YouKn0wWho есть массив $$$a$$$ из $$$n$$$ целых чисел. Помогите ему найти сумму экстремальных значений по всем непустым подмассивам массива $$$a$$$ по модулю $$$998\,244\,353$$$. Если некоторый подмассив встречается в $$$a$$$ несколько раз, его экстремальное значение нужно учесть столько раз, сколько он встречается.
Массив $$$d$$$ является подмассивом массива $$$c$$$, если $$$d$$$ может быть получен из $$$c$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Для каждого набора входных данных выведите одно целое число — сумму экстремальных значений по всем подмассивам $$$a$$$, по модулю $$$998\,244\,353$$$.
4 3 5 4 3 4 3 2 1 4 1 69 8 7264 40515 28226 92776 35285 21709 75124 48163
5 9 0 117
Пусть $$$f(l, r)$$$ обозначает экстремальное значение в подмассиве $$$[a_l, a_{l+1}, \ldots, a_r]$$$.
В первом наборе входных данных:
$$$[5, 4, 3] \rightarrow [\underline{3}, \underline{2}, 4, 3] \rightarrow [3, 2, \underline{2}, \underline{2}, 3] \rightarrow [\underline{1}, \underline{2}, 2, 2, 2, 3]$$$;
Таким образом, общая сумма экстремальных значений всех подмассивов $$$a = 3 + 1 + 1 + 0 + 0 + 0 = 5$$$.
Название |
---|