#P13478. [ABC313Ex] Group Photo

    ID: 12662 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-计数 DP线性 DP排序贪心滚动数组

[ABC313Ex] Group Photo

AT_abc313_h [ABC313Ex] Group Photo

题目描述

存在 2×n+12 \times n + 1 个人需排队照相, 分为两排。

第一排的人高度分别为:a1,a2,a3,...,ana_1, a_2, a_3, ... , a_n。

第二排的人高度分别为:b1,b2,b3,...,bn,bn+1b_1, b_2, b_3, ... , b_n, b_{n+1}。

所有人的身高两两不同。只能在各自所在的那一排内调整顺序。用 ai,bia_i,b_i 表示调整后两排从左至右的身高。合法安排满足下列条件。

  • b1>a1b_1 > a_1
  • bn+1>anb_{n + 1} > a_n
  • $b_{i} > \min(a_i, a_{i - 1}) \text{ }( 2 \le i \le n)$

求有多少种第一排的排列,能为其找到至少一种合法的第二排排列。对同一个第一排排列,无论有多少种合法的第二排排列,都只计一次。

输入格式

共三行。

第一行一个整数表示 nn

第二行 nn 个整数, 分别表示 a1,a2,...,ana_1, a_2, ..., a_n

第三行 n+1n + 1 个整数, 分别表示 b1,b2,...,bn+1b_1, b_2, ..., b_{n + 1}

输出格式

输出一个整数,表示答案对 998244353998244353 取模的结果。

输入输出样例 #1

输入 #1

3
1 12 6
4 3 10 9

输出 #1

2

输入输出样例 #2

输入 #2

1
5
1 10

输出 #2

0

输入输出样例 #3

输入 #3

10
189330739 910286918 802329211 923078537 492686568 404539679 822804784 303238506 650287940 1
125660016 430302156 982631932 773361868 161735902 731963982 317063340 880895728 1000000000 707723857 450968417

输出 #3

3542400

数据范围

1≤n≤50001\le n\le5000,所有身高都是 11 到 10910^9 的整数,且两两不同。

AtCoder 原题