use std::io::prelude::*; fn input(stdin: &mut R) -> String { let mut input = String::new(); stdin.read_line(&mut input).ok(); input } macro_rules! read { ($stdin:expr, [$t:tt; $n:expr]) => { (0..$n).map(|_| read!($stdin, $t)).collect::>() }; ($stdin:expr, [$t:tt]) => { input($stdin).split_whitespace().map(|s| parse!(s, $t)).collect::>() }; ($stdin:expr, ($($t:tt),*)) => {{ let input = input($stdin); let mut iter = input.split_whitespace(); ($(parse!(iter.next().unwrap(), $t)),*) }}; ($stdin:expr, $t:tt) => { parse!(input($stdin).trim(), $t) }; } macro_rules! parse { ($s:expr, Chars) => ($s.chars().collect::>()); ($s:expr, Usize1) => (parse!($s, usize) - 1); ($s:expr, $t:ty) => ($s.parse::<$t>().unwrap()); } #[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)] struct ModInt(i64); impl ModInt { const MOD: i64 = 998_244_353; fn new(x: i64) -> ModInt { Self(x % Self::MOD) } } impl std::ops::Add for ModInt { type Output = Self; fn add(self, other: Self) -> Self { let x = self.0 + other.0; if x < Self::MOD { Self(x) } else { Self(x - Self::MOD) } } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, other: Self) { *self = *self + other; } } impl std::ops::Sub for ModInt { type Output = Self; fn sub(self, other: Self) -> Self { if self.0 < other.0 { Self(self.0 + Self::MOD - other.0) } else { Self(self.0 - other.0) } } } impl std::ops::SubAssign for ModInt { fn sub_assign(&mut self, other: Self) { *self = *self - other; } } impl std::ops::Mul for ModInt { type Output = Self; fn mul(self, other: Self) -> Self { Self::new(self.0 * other.0) } } impl std::ops::MulAssign for ModInt { fn mul_assign(&mut self, other: Self) { *self = *self * other; } } impl std::fmt::Display for ModInt { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result { let x = s.parse()?; Ok(ModInt::new(x)) } } struct FenwickTree { n: usize, init: T, data: Vec, } impl FenwickTree { fn new(n: usize, init: T) -> FenwickTree { FenwickTree { n, init, data: vec![init; n] } } fn add(&mut self, mut p: usize, x: T) { p += 1; while p <= self.n { self.data[p - 1] += x; p += p & (!p + 1); } } fn sum(&self, mut r: usize) -> T { let mut res = self.init; while r > 0 { res += self.data[r - 1]; r -= r & (!r + 1); } res } } fn solve(stdin: &mut R, writer: &mut W) { let n = read!(stdin, usize); let a = read!(stdin, [ModInt]); let mut ord = (0..n).collect::>(); ord.sort_by_key(|&i| a[i]); let mut left_counts = vec![ModInt(0); n]; let mut right_counts = vec![ModInt(0); n]; let mut left_sum = vec![ModInt(0); n]; let mut right_sum = vec![ModInt(0); n]; let mut counts_ft = FenwickTree::new(n, ModInt(0)); let mut sum_ft = FenwickTree::new(n, ModInt(0)); for &i in ord.iter().rev() { left_counts[i] += counts_ft.sum(i); left_sum[i] += sum_ft.sum(i); counts_ft.add(i, ModInt(1)); sum_ft.add(i, a[i]); } let mut counts_ft = FenwickTree::new(n, ModInt(0)); let mut sum_ft = FenwickTree::new(n, ModInt(0)); for &i in ord.iter() { right_counts[i] += counts_ft.sum(n - 1 - i); right_sum[i] += sum_ft.sum(n - 1 - i); counts_ft.add(n - 1 - i, ModInt(1)); sum_ft.add(n - 1 - i, a[i]); } let mut ans = ModInt(0); for i in 0..n { if left_counts[i] == ModInt(0) || right_counts[i] == ModInt(0) { continue; } ans += left_counts[i] * right_sum[i]; ans += right_counts[i] * left_sum[i]; ans += a[i] * left_counts[i] * right_counts[i]; } writeln!(writer, "{}", ans).ok(); } fn main() { let stdin = std::io::stdin(); let stdin = &mut stdin.lock(); let stdout = std::io::stdout(); let writer = &mut std::io::BufWriter::new(stdout.lock()); solve(stdin, writer); }