二人のアルピニスト
题意翻译
高橋君和青木君去徒步爬过了一个著名的山脉。这个山脉由很多个山东西走向依次排开,高橋君从东往西爬,青木君从西往东爬。他们只能记住自己到目前为止经过的最高的山是多高。高橋君记录下的是$T_i$,青木君记下的是$A_i$。
询问山高的可能序列的个数,答案对$1e9 + 7$取模。
如果给出的序列不合法输出$0$。
一句话题意:告诉你一个序列前缀最大值和后缀最大值,求这个序列的可能个数。
范围:
$1 \leq N \leq 1e5$
$1 \leq A_i \leq 1e9 $
$1 \leq T_i \leq 1e9 $
保证T序列单调不降, A序列单调不增。
题目描述
[problemUrl]: https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_c
アルピニストである高橋君と青木君は最近ある有名な山脈を踏破しました。この山脈は$ N $ 個の山からなっており、西から東に向けて山$ 1 $,山$ 2 $,$ ... $,山$ N $と一直線に並んでいます。高橋君は西から、青木君は東からこの山脈を踏破しました。
山$ i $ の高さは$ h_i $ ですが、二人とも各$ h_i $ の値は忘れてしまいました。その代わり、各$ i\ (1≦i≦N) $ に対して、山$ i $ の山頂にたどり着いた時の、それまでに登った山(山$ i $ も含む)の高さの最大値を記録しています。 高橋君の記録した値は$ T_i $ で、青木君の記録した値は$ A_i $ です。
各山の高さ$ h_i $ が正の整数であることはわかっています。山の高さの列としてありうるものが何通りあるかを$ 10^9+7 $ で割ったあまりを求めてください。
ただし記録が間違っていてありうる山の高さの列が存在しないこともあります。この場合は$ 0 $を出力してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ T_1 $ $ T_2 $ $ ... $ $ T_N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $
输出格式
山の高さの列としてありうるものが何通りあるかを $ 10^9+7 $ で割ったあまりを出力せよ。
输入输出样例
输入样例 #1
5
1 3 3 3 3
3 3 2 2 2
输出样例 #1
4
输入样例 #2
5
1 1 1 2 2
3 2 1 1 1
输出样例 #2
0
输入样例 #3
10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5
输出样例 #3
884111967
输入样例 #4
1
17
17
输出样例 #4
1
说明
### 制約
- $ 1≦N≦10^5 $
- $ 1≦T_i≦10^9 $
- $ 1≦A_i≦10^9 $
- $ T_i≦T_{i+1}\ (1≦i≦N-1) $
- $ A_i≧A_{i+1}\ (1≦i≦N-1) $
### Sample Explanation 1
山の高さの列として、 - $ 1,3,2,2,2 $ - $ 1,3,2,1,2 $ - $ 1,3,1,2,2 $ - $ 1,3,1,1,2 $ の$ 4 $通りがありえます。
### Sample Explanation 2
高橋君によると山を全て登り切った後の山の高さの最大値は$ 2 $で、青木君によると$ 3 $なので、記録は矛盾しています。
### Sample Explanation 3
$ 10^9+7 $ で割ったあまりを求めることを忘れないようにしてください。
### Sample Explanation 4
山が一つの山脈もあります。