{"problem":{"name":"Divide a Sequence","description":{"content":"Given is a sequence $A$ of $N$ numbers. There are $2^{N-1}$ ways to divide $A$ into non-empty **contiguous** subsequences $B_1,B_2,\\ldots,B_k$. Find the value below for each of those ways, and print t","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc234_g"},"statements":[{"statement_type":"Markdown","content":"Given is a sequence $A$ of $N$ numbers.\nThere are $2^{N-1}$ ways to divide $A$ into non-empty **contiguous** subsequences $B_1,B_2,\\ldots,B_k$. Find the value below for each of those ways, and print the sum, modulo $998244353$, of those values.\n\n*   $\\prod_{i=1}^{k} (\\max(B_i)-\\min(B_i))$\n\nHere, for a sequence $B_i=(B_{i,1},B_{i,2},\\ldots,B_{i,j})$, $\\max(B_i)$ and $\\min(B_i)$ are defined to be the maximum and minimum values of an element of $B_i$, respectively.\n\n## Constraints\n\n*   $1 \\leq N \\leq 3 \\times 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc234_g","tags":[],"sample_group":[["3\n1 2 3","2\n\nThere are $4$ ways to divide $A=(1,2,3)$ into non-empty contiguous subsequences, as follows.\n\n*   $(1)$, $(2)$, $(3)$\n*   $(1)$, $(2,3)$\n*   $(1,2)$, $(3)$\n*   $(1,2,3)$\n\n$\\prod_{i=1}^{k} (\\max(B_i)-\\min(B_i))$ for these divisions are $0$, $0$, $0$, $2$, respectively. The sum of them, $2$, should be printed."],["4\n1 10 1 10","90"],["10\n699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794","877646588\n\nBe sure to print the sum modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}