## https://yukicoder.me/problems/no/2170 MOD = 998244353 class BinaryIndexTree: """ フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス """ def __init__(self, size): self.size = size self.array = [0] * (size + 1) def add(self, x, a): index = x while index <= self.size: self.array[index] += a self.array[index] %= MOD index += index & (-index) def sum(self, x): index = x ans = 0 while index > 0: ans += self.array[index] ans %= MOD index -= index & (-index) return ans def least_upper_bound(self, value): if self.sum(self.size) < value: return -1 elif value <= 0: return 0 m = 1 while m < self.size: m *= 2 k = 0 k_sum = 0 while m > 0: k0 = k + m if k0 < self.size: if k_sum + self.array[k0] < value: k_sum += self.array[k0] k += m m //= 2 if k < self.size: return k + 1 else: return -1 def main(): N, Q = map(int, input().split()) A = list(map(int, input().split())) lr = [] for _ in range(Q): l, r = map(int, input().split()) lr.append((l - 1, r - 1)) # 各 r について短調減少して行き着く先を求める left_index = [-1] * N l_index = -1 for r in range(N): if l_index == -1: l_index = r else: if A[r - 1] >= A[r]: l_index = r left_index[r] = l_index r_map = {} for i in range(Q): l, r = lr[i] if r not in r_map: r_map[r] = [] r_map[r].append((i, l)) answers = [0] * Q bit = BinaryIndexTree(N) for r in range(N): l_index = left_index[r] if l_index != r: x = pow(2, r - l_index - 1, MOD) bit.add(r + 1, (A[r] * x) % MOD) if r in r_map: for i, l in r_map[r]: target_l = max(l, l_index) x = (bit.sum(r + 1) - bit.sum(target_l + 1)) % MOD x *= pow(pow(2, target_l - l_index, MOD), MOD - 2, MOD) x %= MOD x += A[target_l] x %= MOD answers[i] = x for i in range(Q): print(answers[i]) if __name__ == "__main__": main()