use std::io; const MOD: i64 = 998244353; const HALF: i64 = (MOD + 1) / 2; fn main() { let mut s = String::new(); io::stdin().read_line(&mut s).unwrap(); let v: Vec<_> = s.split_whitespace().collect(); let n: usize = v[0].trim().parse().unwrap(); let q: usize = v[1].trim().parse().unwrap(); let mut s = String::new(); io::stdin().read_line(&mut s).unwrap(); let v = s.split_whitespace(); let mut a: Vec = Vec::new(); for x in v { a.push(x.trim().parse().unwrap()); } let a = a; let mut last = vec![0; n]; for i in 1..n { if a[i] > a[i - 1] { last[i] = last[i - 1]; } else { last[i] = i; } } let last = last; let mut a_sum = vec![0; n + 1]; let mut pow_half = vec![1; n + 1]; let mut mul: i64 = 1; for i in 0..n { a_sum[i + 1] = (a_sum[i] + mul * a[i]) % MOD; mul += mul; if mul >= MOD { mul -= MOD; } pow_half[i + 1] = pow_half[i] * HALF % MOD; } let a_sum = a_sum; let pow_half = pow_half; for _ in 0..q { let mut s = String::new(); io::stdin().read_line(&mut s).unwrap(); let v: Vec<_> = s.split_whitespace().collect(); let mut l: usize = v[0].trim().parse().unwrap(); let mut r: usize = v[1].trim().parse().unwrap(); l -= 1; r -= 1; l = l.max(last[r]); let l = l; let r = r; println!( "{}", ((a_sum[r + 1] - a_sum[l + 1] + MOD) * pow_half[l + 1] + a[l]) % MOD ); } }