AT_abc313_h [ABC313Ex] Group Photo

题目描述

题面描述：

存在 $2 \times n + 1$ 个人需排队照相， 分为两排。

第一排的人高度分别为：$a_1, a_2, a_3, ... , a_n$。

第二排的人高度分别为：$b_1, b_2, b_3, ... , b_n, b_{n+1}$。

你可以自行决定这些人的排列顺序， 使其符合如下条件 ：

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

请问存在合法的第一排排列方案有多少？

输入格式

共三行。

第一行一个整数表示 $n$

第二行 $n$ 个整数， 分别表示 $a_1, a_2, ..., a_n$

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

输出格式

一个整数， 表示答案。

输入输出样例 #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