#include #include constexpr int mod = 998244353; int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int n, q; std::cin >> n >> q; std::vector a(n); for (auto &&x : a) { std::cin >> x; } std::vector last(n); for (int i = 1; i < n; i++) { if (a[i] > a[i - 1]) { last[i] = last[i - 1]; } else { last[i] = i; } } const int64_t half = (mod + 1) / 2; std::vector s(n + 1), pow_half(n + 1); int64_t mul = 1; pow_half[0] = 1; for (int i = 0; i < n; i++) { s[i + 1] = (s[i] + mul * a[i]) % mod; mul += mul; if (mul >= mod) mul -= mod; pow_half[i + 1] = pow_half[i] * half % mod; } for (int i = 0; i < q; i++) { int l, r; std::cin >> l >> r; l--; r--; l = std::max(l, last[r]); std::cout << ((s[r + 1] - s[l + 1]) * pow_half[l + 1] + a[l]) % mod << '\n'; } return 0; }