Problem:


Score : 400 points

Problem Statement

Mountaineers Mr. Takahashi and Mr. Aoki recently trekked across a certain famous mountain range.
The mountain range consists of N mountains, extending from west to east in a straight line as Mt. 1, Mt. 2, ..., Mt. N.
Mr. Takahashi traversed the range from the west and Mr. Aoki from the east.  

The height of Mt. i is h_i, but they have forgotten the value of each h_i.
Instead, for each i (1 ≤ i ≤ N), they recorded the maximum height of the mountains climbed up to the time they reached the peak of Mt. i (including Mt. i).
Mr. Takahashi's record is T_i and Mr. Aoki's record is A_i.  

We know that the height of each mountain h_i is a positive integer.
Compute the number of the possible sequences of the mountains' heights, modulo 10^9 + 7.

Note that the records may be incorrect and thus there may be no possible sequence of the mountains' heights.
In such a case, output 0.

Constraints

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)

Input

The input is given from Standard Input in the following format:

N
T_1 T_2 ... T_N
A_1 A_2 ... A_N

Output

Print the number of possible sequences of the mountains' heights, modulo 10^9 + 7.

Sample Input 1

5
1 3 3 3 3
3 3 2 2 2

Sample Output 1

4

The possible sequences of the mountains' heights are:

1, 3, 2, 2, 2 

1, 3, 2, 1, 2 

1, 3, 1, 2, 2 

1, 3, 1, 1, 2 

for a total of four sequences.

Sample Input 2

5
1 1 1 2 2
3 2 1 1 1

Sample Output 2

0

The records are contradictory, since Mr. Takahashi recorded 2 as the highest peak after climbing all the mountains but Mr. Aoki recorded 3.

Sample Input 3

10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5

Sample Output 3

884111967

Don't forget to compute the number modulo 10^9 + 7.

Sample Input 4

1
17
17

Sample Output 4

1

Some mountain ranges consist of only one mountain.



Sample input:
5
1 3 3 3 3
3 3 2 2 2


Sample output:
4

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
T = getList()
A = getList()

"""
山の高さの列が何通りあるか　dp? 組み合わせ?
dpなら漸化式を考える

5
1 3 3 3 3 高橋くんは左 → 右
3 3 2 2 2 青木くんは右 → 左
最大値のみをレコード

最大値が更新された時のみ高さがわかる
1 3 ? ? ?
? 3 ? ? 2

1 3 ? ? 2
3番目は3以下かつ2以下
4番目は3以下かつ2以下

5
1 1 1 2 2
3 2 1 1 1

1 ? ? 2 ?
3 2 ? ? 1 矛盾
"""

c_t = [-1] * N
c_t[0] = T[0]
for i in range(1, N):
    if T[i] > T[i - 1]:
        c_t[i] = T[i]

c_a = [-1] * N
c_a[N - 1] = A[N - 1]
for i in range(N - 2, -1, -1):
    if A[i] > A[i + 1]:
        c_a[i] = A[i]

c_det = [-1] * N
for i in range(N):
    if c_t[i] >= 0 and c_a[i] >= 0:
        if c_t[i] != c_a[i]:
            print(0)
            exit()
        else:
            c_det[i] = c_t[i]
    elif c_t[i] >= 0:
        c_det[i] = c_t[i]
    elif c_a[i] >= 0:
        c_det[i] = c_a[i]

for i in range(N):
    if c_det[i] > min(T[i], A[i]):
        print(0)
        exit()

ans = 1
for i in range(N):
    if c_det[i] == -1:
        ans *= min(T[i], A[i])
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
mod = int(1e9) + 7
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
LM = [-1 for _ in range(N)]
RM = [-1 for _ in range(N)]
LM[0] = T[0]
S = 1
for i in range(1, N):
    if T[i-1] != T[i]:
        LM[i] = T[i]
RM[-1] = A[-1]
for i in range(N, 1, -1):
    if A[i-1] != A[i-2]:
        RM[i-2] = A[i-2]
for i in range(N):
    if LM[i] != -1 and RM[i] != -1:
        if LM[i] != RM[i]:
            S *= 0
            break
    else:
        if LM[i] == -1 and RM[i] == -1:
            S *= min(T[i], A[i])
            S %= mod
        elif LM[i] != -1 and RM[i] == -1:
            if LM[i] > A[i]:
                S *= 0
                break
        elif LM[i] == -1 and RM[i] != -1:
            if RM[i] > T[i]:
                S *= 0
                break
print(S)

Submission status: Accepted

Solution code:
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve2() -> Any:
    N = read_int()
    T = read_ints()
    A = read_ints()
    upper = [0]*N
    lower = [0]*N
    upper[0] = lower[0] = T[0]
    for i in range(1, N):
        if T[i] > T[i-1]:
            upper[i] = lower[i] = T[i]
        else:
            upper[i] = T[i]
            lower[i] = 1
    if A[N-1] > upper[N-1] or A[N-1] < lower[N-1]:
        return 0
    upper[N-1] = lower[N-1] = A[N-1]
    for i in range(N-2, -1, -1):
        if A[i] > A[i+1]:
            if A[i] > upper[i] or A[i] < lower[i]:
                return 0
            upper[i] = lower[i] = A[i]
        else:
            # 1..A[i]
            if lower[i] > A[i]:
                return 0
            upper[i] = min(upper[i], A[i])
            lower[i] = min(lower[i], A[i])
    answer = 1
    modulo = 10**9+7
    for i in range(N):
        answer = (answer*(upper[i]-lower[i]+1))%modulo
    return answer



if __name__ == '__main__':
    print(solve2())

Submission status: Accepted

Solution code:
import sys
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
if N == 1 and T[0] != A[0]:
    print(0)
    sys.exit()
INF = 10**13
minH = [1]*N
maxH = [INF]*N
pre_ti = 0
MOD = 10**9 + 7
for i, ti in enumerate(T):
    if ti > pre_ti:
        minH[i] = ti
        maxH[i] = ti
    else:
        maxH[i] = min(ti, maxH[i])
    pre_ti = ti
pre_ai = 0
for i, ai in enumerate(A[::-1], 1):
    if ai > pre_ai:
        minH[-i] = ai
        maxH[-i] = ai
    else:
        maxH[-i] = min(ai, maxH[-i])
    pre_ai = ai

ans = 1
for lh, uh in zip(minH, maxH):
    if lh > uh:
        ans = 0
        break
    ans = (ans * (uh-lh+1)) % MOD
print(ans)

Submission status: Accepted

Solution code:
ν=int(input())
τ=list(map(int,input().split()))
α=list(map(int,input().split()))

τ.append(0)
α.append(0)
ρ=1
μ=10**9+7

for ι in range(ν):
  ε=10**10
  if τ[ι]>τ[ι-1]:
    ε=min(1,ε)
    if α[ι]<τ[ι]:
      ε=0
  if α[ι]>α[ι+1]:
    ε=min(1,ε)
    if α[ι]>τ[ι]:
      ε=0
  if τ[ι]<τ[ι-1] or α[ι]<α[ι+1]:
    ε=0
  ε=min(ε,α[ι],τ[ι])
  ρ=(ρ*ε)%μ
print(ρ)

Submission status: Accepted

Solution code:
N = int(input())
Ts = list(map(int, input().split()))
As = list(map(int, input().split()))

maxs = [0] * N
musts = [None] * N
prev = 0
for i in range(N):
    t = Ts[i]
    if prev < t:
        musts[i] = t
    maxs[i] = t
    prev = t

prev = 0
for i in range(N-1, -1, -1):
    a = As[i]
    if prev < a:
        if (musts[i] and musts[i] != a) or maxs[i] < a:
            print(0)
            exit()
        musts[i] = a
    maxs[i] = maxs[i] if maxs[i] < a else a
    prev = a

ans = 1
MOD = 10 ** 9 + 7
for i in range(N):
    if musts[i] is None:
        ans *= maxs[i]
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
tt=[float("inf") for i in range(n)]
ans=[False for i in range(n)]
tmp=0
mod=10**9+7
for i in range(n):
    if t[i]>tmp:
        
        tt[i]=t[i]
        ans[i]=True
        tmp=t[i]
    else:
        tt[i]=tmp
tmp=0
for i in range(n-1,-1,-1):
    if ans[i]==True and a[i]<t[i]:
        print(0)
        exit()
    if a[i]>tmp:
        if ans[i]==True and a[i]!=t[i]:
            print(0)
            exit()
        tt[i]=a[i]
        ans[i]=True
        tmp=a[i]
    else:
        if ans[i]==False and tmp<tt[i]:
            tt[i]=tmp    
tmp=1
for i in range(n):
    if ans[i]==False:
        tmp*=tt[i]
        tmp%=mod
print(tmp%mod)

Submission status: Accepted

Solution code:
n = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 10**9+7
only = [False]*n
h = [0]*n
mx = 0
for i, t in enumerate(T):
    if t > mx:
        only[i] = True
        h[i] = t
        mx = t
    else:
        h[i] = t

mx = 0
for i, a in enumerate(A[::-1]):
    k = n-i-1
    if only[k]:
        if a > mx:
            if h[k] != a:
                print(0)
                exit()
            else:
                mx = a
                continue
        else:
            if h[k] <= a: continue
            else:
                print(0)
                exit()
    else:
        if a > mx:
            if a <= h[k]:
                only[k] = True
                h[k] = a
                mx = a
            else:
                print(0)
                exit()
        else:
            if a <= h[k]:
                h[k] = a

ans = 1
for i in range(n):
    if only[i]: continue
    ans *= h[i]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))
    fixed_t = [0] * N
    max_t = 0
    for i in range(N):
        t = T[i]
        if t > max_t:
            fixed_t[i] = 1
        max_t = max(max_t, t)
    fixed_a = [0] * N
    max_a = 0
    for i in range(N - 1, -1, -1):
        a = A[i]
        if a > max_a:
            fixed_a[i] = 1
        max_a = max(max_a, a)
    ans = 1
    for i in range(N):
        if fixed_t[i] == fixed_a[i] == 1:
            if T[i] != A[i]:
                print(0)
                return
        elif fixed_t[i] == 0 and fixed_a[i] == 1:
            if T[i] < A[i]:
                print(0)
                return
        elif fixed_t[i] == 1 and fixed_a[i] == 0:
            if T[i] > A[i]:
                print(0)
                return
        else:
            ans *= min(A[i], T[i])
            ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ex():
    print(0)
    exit()

MOD=10**9+7
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
if N==1:
    print(1 if A[0]==B[0] else 0)
    exit()

ans=1
tmp=[-1]*N
for i in range(N):
    if i==0 or (i>0 and A[i-1]<A[i]):
        if B[i]<A[i]:
            ex()
        tmp[i]=A[i]
for i in reversed(range(N)):
    if i==N-1 or (i<N-1 and B[i]>B[i+1]):
        if tmp[i]!=-1 and tmp[i]!=B[i]:
            ex()
        if A[i]<B[i]:
            ex()
        tmp[i]=B[i]
for i in range(N):
    if tmp[i]==-1:
        ans=ans*min(A[i],B[i])%MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n=II()
	T=LI()
	A=LI()

	X=[0]*n
	Y=[10**10]*n

	now=0
	for i,v in enumerate(T):
		if now<v:
			X[i]=v
			Y[i]=v
			now=v
		else:
			X[i]=max(X[i],1)
			Y[i]=min(Y[i],now)
	#print(X,Y)

	now=0
	for i,v in enumerate(reversed(A)):
		if now<v:
			if X[n-i-1]<=v<=Y[n-i-1]:
				X[n-i-1]=v
				Y[n-i-1]=v
			else:
				print(0)
				exit()
			now=v
		else:
			X[n-i-1]=max(X[n-i-1],1)
			Y[n-i-1]=min(Y[n-i-1],now)




	#print(X,Y)

	mod=10**9+7
	ans=1

	for i,j in zip(X,Y):
		if i>j:
			print(0)
			exit()
		else:
			ans*=(j-i+1)
			ans%=mod
	print(ans)










if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

ans, frag = 1, 0
for i in range(n):
    if t[i] == a[i] == t[-1] == a[0]:
        frag = 1
    if 0 < i < n - 1 and t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
print(ans * frag)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

ans, frag = 1, 0
for i in range(n):
    if t[i] == a[i] == t[-1] == a[0]:
        frag = 1
    if 0 < i < n - 1 and t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
print(ans if frag == 1 else 0)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

for ti, ai in zip(t, a):
    if ti == ai == t[-1] == a[0]:
        break
else:
    print(0)
    exit()

ans, frag = 1, 0
for i in range(n):
    if t[i] == a[i] == t[-1] == a[0]:
        frag = 1
    if 0 < i < n - 1 and t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
print(ans if frag == 1 else 0)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

for ti, ai in zip(t, a):
    if ti == ai == t[-1] == a[0]:
        break
else:
    print(0)
    exit()

ans = 1
for i in range(1, n - 1):
    if t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

if not any(ti == ai == t[-1] == a[0] for ti, ai in zip(t, a)):
    print(0)
    exit()

ans = 1
for i in range(1, n - 1):
    if t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

tmax, amax = max(t), max(a)
if not any(ti == ai == tmax == amax for ti, ai in zip(t, a)):
    print(0)
    exit()

ans = 1
for i in range(1, n - 1):
    if t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

tmax, amax = max(t), max(a)
if not any(ti == ai == tmax == amax for ti, ai in zip(t, a)):
    print(0)
    exit()

ans = 1
for i in range(1, n - 1):
    if t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
else:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

tmax, amax = max(t), max(a)
if not any(ti == ai == tmax == amax for ti, ai in zip(t, a)):
    print(0)
    exit()

ans = 1
for i in range(1, n - 1):
    if ((t[i - 1] < t[i] and t[i] > a[i])
        or (a[i] > a[i + 1] and t[i] < a[i])):
            print(0)
            break
    elif t[i - 1] == t[i] and a[i] == a[i + 1]:
        ans = ans * min(t[i], a[i]) % mod
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

if N == 1:
    if T[0] == A[0]:
        print(1)
    else:
        print(0)
    sys.exit()

mod = 10**9 + 7
ans = 1
for i in range(N):
    if i == 0:
        if A[i] < T[i]:
            print(0)
            sys.exit()
    elif i == N-1:
        if T[i] < A[i]:
            print(0)
            sys.exit()
    else:
        if T[i-1] < T[i] and A[i+1] < A[i] and T[i] != A[i]:
            print(0)
            sys.exit()
        else:
            if T[i-1] < T[i]:
                if A[i] < T[i]:
                    print(0)
                    sys.exit()
            elif A[i+1] < A[i]:
                if T[i] < A[i]:
                    print(0)
                    sys.exit()
            else:
                ans *= min(T[i], A[i])
                ans %= mod

print(ans)

Submission status: Accepted

Solution code:
p = 10**9+7
N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
H = [0 for _ in range(N)]
flag = 0
if T[N-1]!=A[0]:
    flag = 1
hmax = A[0]
if flag==0:
    indmaxT=0
    H[0] = T[0]
    for i in range(1,N):
        if T[i]>T[i-1]:
            H[i] = T[i]
            if H[i]==hmax:
                indmaxT = i
                break
    indmaxA = N-1
    H[N-1] = A[N-1]
    for i in range(N-2,-1,-1):
        if A[i]>A[i+1]:
            H[i]=A[i]
            if H[i]==hmax:
                indmaxA = i
                break
    if indmaxA<indmaxT:
        flag = 1
if flag==1:
    print(0)
else:
    cnt = 1
    cur = 0
    for i in range(1,indmaxT):
        if H[i]==0:
            cnt = (cnt*H[cur])%p
        elif H[i]>0:
            cur = i
    cur = N-1
    for i in range(N-2,indmaxA,-1):
        if H[i]==0:
            cnt = (cnt*H[cur])%p
        elif H[i]>0:
            cur = i
    for i in range(indmaxT+1,indmaxA):
        cnt = (cnt*hmax)%p
    print(cnt)

Submission status: Accepted

Solution code:
import sys


def LI():
    return list(map(int, input().split()))


mod = pow(10, 9)+7
N = int(input())
T = LI()
A = LI()
ans = 1
if N == 1:
    if T == A:
        print(1)
    else:
        print(0)
    sys.exit()
if N == 2:
    if T[1] == A[0]:
        print(1)
    else:
        print(0)
if T[N-1] != A[0]:
    print(0)
    sys.exit()
for i in range(1, N-1):
    if T[i-1] != T[i]:
        if A[i] < T[i]:
            print(0)
            sys.exit()
        continue
    if A[i] != A[i+1]:
        if A[i] > T[i]:
            print(0)
            sys.exit()
        continue
    ans = (ans * min(T[i], A[i])) % mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    N = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))

    if T[-1] != A[0]:
        print(0)
        exit()

    upper = T[:]
    flag = [0] * N

    # Tくんの目線で見る
    now = 0
    for i in range(N):
        if T[i] > now:
            flag[i] = 1
            now = T[i]

    # A君の目線で見る
    now = 0
    for i in range(N):
        if flag[N-1-i] and T[N-1-i] > A[N-1-i]:
            print(0)
            exit()

        if A[N-1-i] > now:
            flag[N-1-i] = 1
            now = A[N-1-i]

        upper[N-1-i] = min(upper[N-1-i],A[N-1-i])

    ans = 1
    m = 10**9+7
    for i in range(N):
        if flag[i]==0:
            ans *= upper[i]
            ans %= m
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
T = LI()
A = LI()
mod = 10**9+7

minimum = [1]*N  # 山i(0-index)の高さとしてありうる最小値
maximum = [0]*N  # 山i(0-index)の高さとしてありうる最大値

for i in range(N):
    if i == 0:
        minimum[i] = T[i]
        maximum[i] = T[i]
    else:
        if T[i] != T[i-1]:
            minimum[i] = T[i]
            maximum[i] = T[i]
        else:
            maximum[i] = T[i]

for i in range(N-1,-1,-1):
    if i == N-1:
        minimum[i] = max(minimum[i],A[i])
        maximum[i] = min(maximum[i],A[i])
    else:
        if A[i] != A[i+1]:
            minimum[i] = max(minimum[i],A[i])
            maximum[i] = min(maximum[i],A[i])
        else:
            maximum[i] = min(maximum[i],A[i])

ans = 1
for i in range(N):
    if maximum[i] >= minimum[i]:
        ans *= maximum[i]-minimum[i]+1
        ans %= mod
    else:
        print(0)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
Ts = list(mapint())
As = list(mapint())
mod = 10**9 + 7

maxi = [10**18]*N
confirmed = [-1]*N

now = 0
for i in range(N):
    t = Ts[i]
    if t>now:
        now = t
        confirmed[i] = t
    else:
        maxi[i] = t

now = 0
for i in range(N-1, -1, -1):
    a = As[i]
    if a>now:
        now = a
        if maxi[i]<a:
            print(0)
            exit()          
        if confirmed[i]==-1:
            confirmed[i] = a
        elif confirmed[i]!=a:
            print(0)
            exit()
    else:
        maxi[i] = min(maxi[i], a)

ans = 1
for i in range(N):
    if confirmed[i]!=-1:
        continue
    ans *= maxi[i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))

mod = 10 ** 9 + 7

yama = [0] * n

# tは、t[i] == t[i + 1]だったら左の以外全部ありうる
yama[0] = t[0]
if t[0] > a[0]:
    print(0)
    exit()
for i in range(n - 1):
    if t[i] < t[i + 1]:
        # i + 1の高さ確定
        yama[i + 1] = t[i + 1]
        if t[i + 1] > a[i + 1]:
            print(0)
            exit()
for i in range(n - 1, 0, -1):
    if a[i - 1] > a[i]:
        yama[i - 1] = a[i - 1]
        if a[i - 1] > t[i - 1]:
            print(0)
            exit()
if a[n - 1] > t[n - 1]:
    print(0)
    exit()
yama[n - 1] = a[n - 1]

ans = 1
for i in range(1, n - 1):
    if yama[i] == 0:
        ans = (ans * min(a[i], t[i])) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))

    check = [False] * n
    check[0] = check[-1] = True
    res = [f_inf] * n
    res[0] = T[0]
    res[-1] = A[-1]
    for i in range(1, n):
        if T[i - 1] != T[i] or T[i] == 1:
            check[i] = True
        res[i] = min(res[i], T[i])

    for j in reversed(range(n - 1)):
        if A[j + 1] != A[j] or A[j] == 1:
            check[j] = True
        res[j] = min(res[j], A[j])

    ma = 0
    for i in range(n):
        if check[i]:
            if res[i] > ma:
                ma = res[i]
        if T[i] > ma:
            print(0)
            exit()

    ma = 0
    for i in reversed(range(n)):
        if check[i]:
            if res[i] > ma:
                ma = res[i]
        if A[i] > ma:
            print(0)
            exit()

    ans = 1
    for k in range(n):
        if not check[k]:
            ans *= res[k]
            ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
arr = [[1] * n for _ in range(4)]
t = list(map(int, input().split()))
a = list(map(int, input().split()))[::-1]

MOD = 10**9 + 7

max_t = 0
max_a = 0

for i in range(n):
    if max_t < t[i]:
        arr[0][i] = t[i]
        arr[1][i] = t[i]
        max_t = t[i]
    else:
        arr[1][i] = t[i]
    if max_a < a[i]:
        arr[2][i] = a[i]
        arr[3][i] = a[i]
        max_a = a[i]
    else:
        arr[3][i] = a[i]

arr[2] = arr[2][::-1]
arr[3] = arr[3][::-1]

ans = 1
for i in range(n):
    ans *= max(min(arr[1][i], arr[3][i]) - max(arr[0][i], arr[2][i]) + 1, 0)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
ans = 1; MOD = pow(10,9)+7
if N == 1:
  if A[0] == T[0]:
    print(1)
  else:
    print(0)
  exit()
for i in range(N):
  if i == 0: #T[0]じゃないとダメ
    if A[i] == A[i+1]: #なんでもおk
      fac = 1
    else: #A[i]じゃなとダメ
      if A[i] > T[0]: #矛盾
        fac = 0
      else:
        fac = 1
  elif i < N-1: #間
    if T[i] == T[i-1]: #T[i]以下ならなんでもおｋ
      if A[i] == A[i+1]: #A[i]以下ならなんでもおｋ
        fac = min(T[i],A[i])
      else: #A[i]じゃないとダメ
        if A[i] > T[i]: #矛盾
          fac = 0
        else:
          fac = 1
    else: #T[i]じゃないとだめ
      if A[i] == A[i+1]: #A[i]以下ならなんでもｋ
        if T[i] > A[i]: #矛盾
          fac = 0
        else:
          fac = 1
      else: #A[i]じゃないとだめ
        if T[i] == A[i]:
          fac = 1
        else:
          fac = 0
  else: #i = N-1。A[i]じゃないとダメ
    if T[i] == T[i-1]: #T[i]以下ならなんでもおｋ
      if A[i] > T[i]: #矛盾
        fac = 0
      else:
        fac = 1
    else: #T[i]じゃないとダメ
      if T[i] == A[i]:
        fac = 1
      else:
        fac = 0
  ans = (ans*fac)%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
T = LI()
A = LI()
mod = 10**9+7

minimum = [1]*N
maximum = [0]*N

for i in range(N):
    if i == 0:
        minimum[i] = T[i]
        maximum[i] = T[i]
    else:
        if T[i] != T[i-1]:
            minimum[i] = T[i]
            maximum[i] = T[i]
        else:
            maximum[i] = T[i]

for i in range(N-1,-1,-1):
    if i == N-1:
        minimum[i] = max(minimum[i],A[i])
        maximum[i] = min(maximum[i],A[i])
    else:
        if A[i] != A[i+1]:
            minimum[i] = max(minimum[i],A[i])
            maximum[i] = min(maximum[i],A[i])
        else:
            maximum[i] = min(maximum[i],A[i])

ans = 1
for i in range(N):
    if maximum[i] >= minimum[i]:
        ans *= maximum[i]-minimum[i]+1
        ans %= mod
    else:
        print(0)
        exit()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
tl = list(map(int, input().split()))
al = list(map(int, input().split()))

if tl[-1] != al[0]:
    print(0)
    exit()

ans = 1
for i in range(1,n-1):
    if tl[i] > tl[i-1] or al[i] > al[i+1]:
        ans *= 1
    else:
        ans *= min(tl[i],al[i])

    if tl[i] > tl[i-1] and tl[i] > al[i]:
        print(0)
        exit()
    elif al[i] > al[i+1] and al[i] > tl[i]:
        print(0)
        exit()
    ans%=(10**9+7)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def err():
    print(0)
    quit()

n = inp()
a = inpl()
b = inpl()
if a[-1] != b[0]: err()
de = [-1] * n
mx = [INF] * n
now = -1
for i in range(n):
    if a[i] > now:
        now = a[i]
        de[i] = now
    else:
        mx[i] = now
now = -1
for i in range(n)[::-1]:
    if b[i] > now:
        now = b[i]
        if de[i] != -1 and de[i] != now:
            err()
        de[i] = now
    else:
        if now < de[i]: err()
        mx[i] = min(mx[i], now)
res = 1
for i in range(n):
    if de[i] == -1:
        res *= mx[i]
        res %= mod
print(res)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
tlst = list(map(int, input().split()))
alst = list(map(int, input().split()))
cand_t = [[1, 1] for _ in range(n)]
cand_t[0] = [tlst[0], tlst[0]]
for i in range(1, n):
    if tlst[i] == tlst[i - 1]:
        cand_t[i][1] = tlst[i]
    else:
        cand_t[i] = [tlst[i], tlst[i]]
cand_a = [[1, 1] for _ in range(n)]
cand_a[-1] = [alst[-1], alst[-1]]
for i in range(n - 2, -1, -1):
    if alst[i] == alst[i + 1]:
        cand_a[i][1] = alst[i]
    else:
        cand_a[i] = [alst[i], alst[i]]
ans = 1
for (t_r, t_h), (a_r, a_h) in zip(cand_t, cand_a):
    r = max(t_r, a_r)
    h = min(t_h, a_h)
    if r > h:
        print(0)
        break
    ans *= (h - r + 1)
    ans %= MOD
else:
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ht=list(map(int,input().split()))
ha=list(map(int,input().split()))
ans=ha[0]==ht[-1] and ha[ht.index(ht[-1])]==ht[-1]
m=10**9+7
cnt=0
for i,(t,a) in enumerate(zip(ht[1:n-1],ha[1:n-1])):
  if t<a and t==ht[i]:ans*=t
  elif t>a and a==ha[i+2]:ans*=a
  cnt+=t==a
  ans%=m
cnt+=(ha[0]==ht[0])+(ha[-1]==ht[-1])
ans*=pow(max(ha),max(cnt-2,0),m)
print(ans%m)

Submission status: Accepted

Solution code:
inf = 10 ** 18
mod = 10 ** 9 + 7
n = int(input())
t = [0] + list(map(int, input().split())) + [inf]
a = [inf] + list(map(int, input().split())) + [0]
ans = 1
for i in range(1, n + 1):
    if t[i - 1] < t[i]:
        ans *= 0 if t[i] > a[i] else 1
    if a[i + 1] < a[i]:
        ans *= 0 if t[i] < a[i] else 1
    if t[i - 1] == t[i] and a[i + 1] == a[i]:
        ans *= min(t[i], a[i])
        ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ai = [-1] * n
bi = [-1] * n
r = [-1] * n
ai[0]=a[0]
bi[-1]=b[-1]
for i in range(1,n):
  if a[i] > a[i-1]:
    ai[i] = a[i]
for i in range(n-2,-1,-1):
  if b[i] > b[i+1]:
    bi[i] = b[i]
ret = 1
r = [0] * n
for i in range(n):
  if ai[i]!=bi[i] and ai[i]!=-1 and bi[i]!=-1:
    print(0)
    exit()
  elif ai[i]==-1 and bi[i]==-1:
    ret *= min(a[i], b[i])
    ret %= 10**9+7
  else:
    r[i]=max(ai[i], bi[i])
x = 0
for i in range(n):
  x = max(x, r[i])
  if x!=a[i]:
    print(0)
    exit()
x = 0
for i in range(n-1, -1, -1):
  x = max(x, r[i])
  if x!=b[i]:
    print(0)
    exit()
print(ret)