#P9091. 「HNOI2021 省集 Day7」乐

    ID: 5175 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-动态规划计数 DP组合数学补集计数多项式与生成函数卷积转化离线与分治分治 FFTNTT数论模逆元CF2600

「HNOI2021 省集 Day7」乐

题目描述

给定一个单调不降的正整数序列 v1,…,vnv_1,\ldots,v_n。

定义一个“悦耳的旋律”ss:

  • 对所有 1≤i≤n1\le i\le n,1≤si≤vi1\le s_i\le v_i。
  • 序列不存在非空的真 border:不存在 1≤k<n1\le k<n,使前 kk 项与后 kk 项完全相同。

求满足上述条件的、长度为 nn 的正整数序列 ss 的数量,答案对 998244353998244353 取模。

输入格式

从标准输入读入。

第一行为一个正整数 nn。

接下来一行 nn 个正整数 viv_i。

输出格式

输出到标准输出。

仅一行一个整数,表示你的答案。

样例

样例 1

3
2 3 3
12

分别为:

  • {1,1,2}\{1, 1, 2\};
  • {1,2,2}\{1, 2, 2\};
  • {1,3,2}\{1, 3, 2\};
  • {1,1,3}\{1, 1, 3\};
  • {1,2,3}\{1, 2, 3\};
  • {1,3,3}\{1, 3, 3\};
  • {2,1,1}\{2, 1, 1\};
  • {2,2,1}\{2, 2, 1\};
  • {2,3,1}\{2, 3, 1\};
  • {2,1,3}\{2, 1, 3\};
  • {2,2,3}\{2, 2, 3\};
  • {2,3,3}\{2, 3, 3\};

样例 2、3、4

见附加文件中 music*.in 和 music*.out。

数据范围

  • 对于 10%10\% 的数据,n≤6n\le 6,vi≤6v_i\le 6。
  • 对于 30%30\% 的数据,n≤5×103n\le 5\times 10^3。
  • 对于另外 25%25\% 的数据,viv_i 全部相同。
  • 对于 80%80\% 的数据,n≤105n\le 10^5。
  • 对于 100%100\% 的数据,1≤n≤1061\le n\le 10^6,1≤vi≤9982443531\le v_i\le 998244353,vi≤vi+1v_i\le v_{i+1}。