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:
n = int(input())
ans = [0]*n
ans2 = [0]*n
a=list(map(int, input().split()))
b=list(map(int, input().split()))
amax=0
bmax=0

for i in range(n//2):
  if a[i]>amax:
    amax=a[i]
    ans[i]=1
    ans2[i]=a[i]
  elif a[i]<amax:
    print(0)
    quit()
  else:
    ans[i]=amax
  if b[-(i+1)]>bmax:
    bmax=b[-(i+1)]
    ans[-(i+1)]=1
    ans2[-(i+1)]=b[-(i+1)]
  elif b[-i-1]<bmax:
    print(0)
    quit()
  else:
    ans[-(i+1)]=bmax

if n%2==1:  
  i=n//2
  if a[i]>amax:
    amax=a[i]
    ans[i]=1
    ans2[i]=a[i]
  elif a[i]<amax:
    print(0)
    quit()
  else:
    ans[i]=amax
    
for i in range(n//2, n):
  if a[i]>amax:
    amax=a[i]
    if ans[i]==1 and a[i]!=ans2[i]:
        print(0)
        quit()
    elif ans[i] != 1 and ans[i]<a[i]:
      print(0)
      quit()
    ans[i]=1
  elif a[i]<amax:
    print(0)
    quit()
  else:
    ans[i]=min(amax, ans[i])
  if b[-(i+1)]>bmax:
    bmax=b[-(i+1)]
    if ans[-(i+1)]==1 and b[-(i+1)]!=ans2[-(i+1)]:
        print(0)
        quit()
    elif ans[-i-1]!=1 and ans[-i-1]<b[-i-1]:
      print(0)
      quit()
    ans[-(i+1)]=1
  elif b[-i-1]<bmax:
    print(0)
    quit()
  else:
    ans[-(i+1)]=min(bmax, ans[-(i+1)])
    
kotae=1
for i in range(n):
  kotae*=ans[i]
  kotae%=(10**9+7)
print(kotae)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N = I()
A = IL()
B = IL()

def koho(p,q):
  p1,q1 = p
  p2,q2 = q
  p = max(p1,p2)
  q = min(q1,q2)
  if p>q:
    print(0)
    exit()
  else:
    return (p,q)

D = [(1,INF) for i in range(N)]

prev = 0
for i in range(N):
  a = A[i]
  if a > prev:
    temp = (a,a)
  else:
    temp = (1,a)
  D[i] = koho(D[i],temp)
  prev = a
prev = 0
for i in range(N)[::-1]:
  a = B[i]
  if a > prev:
    temp = (a,a)
  else:
    temp = (1,a)
  D[i] = koho(D[i],temp)
  prev = a
ans = 1
for a,b in D:
  ans *= b-a+1
  ans %= MOD
print(ans)

Submission status: Accepted

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

prev = 0
inds = []
for t in Ts:
    if prev < t:
        inds.append((t,1))
    else:
        inds.append((t,0))
    prev = t
indsA = []
prev = 0
for a in As[::-1]:
    if prev < a:
        indsA.append((a,1))
    else:
        indsA.append((a,0))
    prev = a
# print(inds, indsA[::-1])
# if Ts[-1] != As[0]:
#     print(0)
#     exit()
ans = 1
MOD = 10**9 + 7
for it, ia in zip(inds, indsA[::-1]):
    # print(it,ia)
    if it[1] == 1 and ia[1] == 1:
        if it[0] != ia[0]:
            # 矛盾
            print(0)
            exit()
    elif it[1] == 1 and ia[1] == 0:
        # print("t",it,ia)
        if it[0] > ia[0]:
            print(0)
            exit()
    elif it[1] == 0 and ia[1] == 1:
        # print("a",it,ia)
        if it[0] < ia[0]:
            print(0)
            exit()
    else:
        mn = min(it[0],ia[0])
        ans *= mn
        ans %= MOD
    # print(it,ia,ans)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
T=list(map(int,input().split()))
A=list(map(int,input().split()))
X=[T[0]]
Y=[A[-1]]
for i in range(N-1):
  if T[i]<T[i+1]:
    X.append(T[i+1])
  else:
    X.append(0)
  if A[-i-1]<A[-i-2]:
    Y.append(A[-i-2])
  else:
    Y.append(0)
Y=Y[::-1]
for i in range(N):
  if min(X[i],Y[i]) and X[i]!=Y[i]:
    print(0)
    exit()
mod=10**9+7
Z=[max(X[i],Y[i]) for i in range(N)]
C=0
for i in range(N):
  C=max(C,Z[i])
  if C!=T[i]:
    print(0)
    exit()
C=0
for i in range(N):
  C=max(C,Z[-i-1])
  if C!=A[-i-1]:
    print(0)
    exit()
mod=10**9+7
P=1
for i in range(N):
  if Z[i]==0:
    P=P*min(A[i],T[i])%mod
print(P)

Submission status: Accepted

Solution code:
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
mod=pow(10,9)+7
ans=[[0,0] for _ in range(n)]
pre=0
for i in range(n):
  if t[i]>pre:
    ans[i]=[t[i],1]
  else:
    ans[i]=[t[i],0]
  pre=t[i]
#print(ans)
pre=0
for i in range(n-1,-1,-1):
  if a[i]>pre:
    if ans[i][1]==0 and ans[i][0]<a[i]:
      print(0)
      exit()
    elif ans[i][1]==1 and ans[i][0]!=a[i]:
      print(0)
      exit()
    else:
      ans[i]=[a[i],1]
  else:
    if ans[i][1]==0:
      ans[i][0]=min(ans[i][0],a[i])
    elif ans[i][1]==1 and ans[i][0]>a[i]:
      print(0)
      exit()
  pre=a[i]
b=1
for x,y in ans:
  if y==1:continue
  b*=x
  b%=mod
print(b)

Submission status: Accepted

Solution code:
#CODE FESTIVAL 2016 qual C-C 二人のアルピニスト
"""
左右一列に並んでいる山を、左右から見ていった時に今まで見た中の最大値が分かる。
この状態で、山の高さの列が何通りあるか求めよ。

単純に、山の高さの"幅"を求めて、その分だけかけ合わせれば良さそう。

辻褄が合わないのは
1.高さが確定している場所同士で、辻褄が合わない
2.片方の高さが確定している場所で、もう片方の値がそれより小さい
このとき0
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
L = list(map(int,readline().split()))
R = list(map(int,readline().split()))
mod = 10**9 + 7

mx = 0
L1 = []
for i in range(n):
    if mx < L[i]:
        L1.append((1,L[i]))
        mx = L[i]
    else:
        L1.append((0,L[i]))

R1 = []
mx = 0
for i in range(n-1,-1,-1):
    if mx < R[i]:
        R1.append((1,R[i]))
        mx = R[i]
    else:
        R1.append((0,R[i]))
R1.reverse()
ans = 1
for i in range(n):
    if L1[i][0] == 1:
        if R1[i][0] == 1:
            if L1[i][1] != R1[i][1]:
                ans = 0
                break
        else:
            if L1[i][1] > R1[i][1]:
                ans = 0
                break
    elif R1[i][0] == 1:
        if R1[i][1] > L1[i][1]:
            ans = 0
            break
    else:
        ans *= min(L1[i][1],R1[i][1])
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
T = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))
mod = 10**9+7

mt = T[-1]
ma = A[0]
if mt != ma:
    print(0)
else:
    ans = 1
    for i in range(1, n-1):
        if T[i-1] == T[i] and A[i] == A[i+1]:
            ans *= min(T[i], A[i])
            ans %= mod
        if T[i] == A[i] and (T[i] != mt or A[i] != ma):
            print(0)
            break
        if ((T[i] > T[i-1] and T[i] > A[i]) or
            (A[i] > A[i+1] and T[i] < A[i])):
            print(0)
            break
    else:
        print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t = [0]+list(map(int,input().split()))+[0]
s = [0]+list(map(int,input().split()))+[0]

mod = 10**9+7
if max(t) != max(s):
    print(0)
    exit()
ans = 1
for i in range(1,n+1):
    d = False
    if t[i] != t[i-1]:
        d = True
        x = t[i]
    if s[i] != s[i+1]:
        if d:
            if x != s[i]:
                print(0)
                exit()
        else:
            d = True
            x = s[i]
    if d:
        if x > t[i] or x > s[i]:
            print(0)
            exit()
    if not d:
        ans *= min(s[i],t[i])
        ans %= mod
print(ans%mod)

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def solve():
        ans = 1
        for i in range(n):
            if t_info[i] and a_info[i]:
                # fixed 同士のチェック
                if T[i] != A[i]:
                    return 0
            elif t_info[i]:
                # a_info の条件は大丈夫か？
                if T[i] > A[i]:
                    return 0
            elif a_info[i]:
                # t_info の条件は大丈夫か？
                if A[i] > T[i]:
                    return 0
            else:
                # どちらも上界しか分からん
                up_boundary = min(T[i], A[i])
                ans = (ans * up_boundary) % mod
        return ans

    
    n = ii()
    T = lmi()
    A = lmi()

    t_info = [False] * n    # bool (fixed?)
    for i in range(n):
        if i == 0 or T[i] > T[i-1]:
            t_info[i] = True
    
    a_info = [False] * n
    for i in range(n-1, -1, -1):
        if i == n - 1 or A[i] > A[i+1]:
            a_info[i] = True
    
    print(solve())

            


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
H = [0]*N
flag=0

H[0]=T[0]
for i in range(1,N):
    if T[i]!=T[i-1]:
        H[i]=T[i]
    else:
        H[i] = -1*T[i]

H[N-1]=A[N-1]

for i in range(1,N):
    if A[N-i-1]!=A[N-i]:
        if (H[N-i-1]<0 and A[N-i-1] > -1*H[N-i-1]) or (H[N-i-1]>0 and A[N-i-1] > H[N-i-1]):
            flag=1
            break
        H[N-i-1]=A[N-i-1]
    else:
        H[N-i-1]=max(-1*A[N-i-1],H[N-i-1])
if N==1:
    if A[0]==T[0]:
        print(1)
    else:
        print(0)

elif flag==0:
    p = 10**9+7
    out = 1
    for i in range(N):
        if H[i]<0:
            out = out * (-1*H[i]) % p
    print(out)
else:
    print(0)

Submission status: Accepted

Solution code:
Q = 10**9+7
def main():
    N = int( input())
    T = list( map( int, input().split()))
    A = list( map( int, input().split()))
    ANS = [0]*N
    now = 0
    AC = [False]*N
    for i in range(N):
        if now < T[i]:
            ANS[i] = T[i]
            AC[i] = True
        now = T[i]
    now = 0
    for i in range(N-1,-1,-1):
        if now < A[i]:
            if AC[i]:
                if A[i] != T[i]:
                    print(0)
                    return
            else:
                if A[i] > T[i]:
                    print(0)
                    return
                else:
                    ANS[i] = A[i]
        now = A[i]
    # for i in range(N):
    #     if ANS[i] == 0:
    #         ANS[i] = min(A[i],B[i])
    ans = 1
    for i in range(N):
        if ANS[i] == 0:
            ans *= min(A[i],T[i])
            ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))[::-1]
    mod = 1000000007
    if n == 1:
        if T[0] == A[0]:
            print(1)
        else:
            print(0)
        exit()
    INF = 1e+10
    ans = [[0, INF] for _ in range(n)]
    ans[0] = [1, T[0]]
    ans[-1] = [1, A[0]]
    for i, (t, a) in enumerate(zip(T[1:], A[1:])):
        i += 1
        an = ans[i]
        if t > T[i - 1]:
            if (an[0] == 0 and an[1] >= t) or (an[0] == 1 and an[1] == t):
                ans[i] = [1, t]
            else:
                print(0)
                exit()
        else:
            if an[0] == 0:
                ans[i][1] = min(ans[i][1], t)
            else:
                if an[1] > t:
                    print(0)
                    exit()
                else:
                    pass
        an = ans[-(i + 1)]
        if a > A[i - 1]:
            if (an[0] == 0 and an[1] >= a) or (an[0] == 1 and an[1] == a):
                ans[-(i + 1)] = [1, a]
            else:
                print(0)
                exit()
        else:
            if an[0] == 0:
                ans[-(i + 1)][1] = min(ans[-(i + 1)][1], a)
            else:
                if an[1] > a:
                    print(0)
                    exit()
                else:
                    pass
    c = 1
    for a in ans:
        if a[0] == 0:
            c = c * a[1] % mod
    print(c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
m=[0]*n
MOD=10**9+7
m[0]=t[0]
for i in range(1,n):
  if t[i-1]<t[i]:
    m[i]=t[i]
  else:
    m[i]=-1*t[i]
if m[n-1]>0 and m[n-1]!=a[n-1]:
  print(0)
  sys.exit()
if m[n-1]<0 and -1*m[n-1]<a[n-1]:
  print(0)
  sys.exit()
m[n-1]=a[n-1]
for i in range(n-2,-1,-1):
  if a[i+1]<a[i]:
    if (m[i]>0 and m[i]!=a[i]) or (m[i]<0 and -1*m[i]<a[i]):
      print(0)
      sys.exit()
    m[i]=a[i]
  else:
    m[i]=max(m[i],-1*a[i])
ans=1
for i in range(n):
  if m[i]<0:
    ans=(ans*-1*m[i])%MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

al = list(map(int,input().split()))
tl = list(map(int,input().split()))


for i in range(n-1):
    if al[i] > al[i+1]:
        print(0)
        exit()
    if tl[i] < tl[i+1]:
        print(0)
        exit()

ans = 1
for i in range(n):
    a = False
    t = False
    if i != 0:
        if al[i] != al[i-1]:
            a = True
    else:
        a = True
    if i != n-1:
        if tl[i] != tl[i+1]:
            t = True
    else:
        t = True
    if a and t:
        if al[i] != tl[i]:
            print(0)
            exit()
    elif a:
        if al[i] > tl[i]:
            print(0)
            exit()
    elif t:
        if al[i] < tl[i]:
            print(0)
            exit()
    else:
        ans *= min(al[i], tl[i])
        ans %= 10**9 + 7

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = [0] + list(map(int, input().split())) + [0]
A = [0] + list(map(int, input().split())) + [0]

MOD = 10 ** 9 + 7


def imp():
    print(0)
    exit()


ans = 1
for i in range(1, N + 1):
    if T[i - 1] < T[i]:
        if A[i] < T[i]:
            imp()
    elif A[i] > A[i + 1]:
        if T[i] < A[i]:
            imp()
    else:
        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()))
#nは10**5以下

kakute=[0]*n
kakute[0]=1

if n==1:
    if t[0]!=a[0]:
        print(0)
        exit()

for i in range(1,n):
    if t[i]>t[i-1]:
        kakute[i]=1

a=a[::-1]
ans=1

for i in range(1,n):
    index=n-i-1
    #青木が確定したとき
    if a[i]>a[i-1]:
        #矛盾ないか
        if a[i]>t[index]:
            print(0)
            exit()
        #青木＆高橋確定
        elif kakute[index]==1:
            if a[i] != t[index]:
                print(0)
                exit()
    #青木は確定じゃない
    else:
        #高橋確定
        if kakute[index]==1:
            if t[index]>a[i]:
                print(0)
                exit()
        #誰も確定していない
        else:
            ans=ans*min(a[i],t[index])%(10**9+7)

print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

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

fix = [False for i in range(N)]
fix[0] = True
for i in range(1, N):
    if T[i] > T[i-1]:
        fix[i] = True

# print(fix)

if fix[N-1] is True and T[N-1] != A[N-1]:
    print(0)
    exit()
else:
    fix[N-1] = True
    T[N-1] = A[N-1]

for j in range(N-2, 0, -1):
    if A[j] > A[j+1]:
        if fix[j] is True and A[j] != T[j]:
            print(0)
            exit()
        else:
            fix[j] = True
            T[j] = A[j]
    elif fix[j] is True and T[j] > A[j]:
        print(0)
        exit()
    elif fix[j] is not True:
        T[j] = min(T[j], A[j])


MOD = 10**9 + 7
ans = 1
for i in range(N):
    if fix[i] is False:
        ans *= T[i]
        ans %= MOD
print(ans)

Submission status: Accepted

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

N = int(input())
T = [0]+list(map(int, input().split()))+[0]
A = [0]+list(map(int, input().split()))+[0]
ans = 1
MOD = 10**9+7

for i in range(1, N+1):
    if T[i]!=T[i-1] and A[i]!=A[i+1]:
        if T[i]!=A[i]:
            print(0)
            exit()
    elif T[i]!=T[i-1] and A[i]==A[i+1]:
        if T[i]>A[i]:
            print(0)
            exit()
    elif T[i]==T[i-1] and A[i]!=A[i+1]:
        if A[i]>T[i]:
            print(0)
            exit()
    else:
        ans *= min(T[i], A[i])
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
n_cases = [0]*n
n_cases[0] = n_cases[-1] = 1
height = [0]*n
if T[-1] != A[0]:
    print(0)
    exit()
height[0] = T[0]
height[-1] = A[-1]
for i, (t1, t2) in enumerate(zip(T, T[1:]), 1):
    if t1 != t2:
        n_cases[i] = 1
        height[i] = t2

for i, (a1, a2) in enumerate(zip(A[::-1], A[::-1][1:]), 2):
    if a1 != a2:
        n_cases[-i] = 1
        if height[-i] == a2 or (height[-i] == 0 and a2 <= T[-i]):
            continue
        print(0)
        exit()

for i, (t, a) in enumerate(zip(T, A)):
    if n_cases[i]:
        continue
    n_cases[i] = min(t, a)


ans = 1
for x in n_cases:
    ans *= x
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
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()))

    pattern = [0] * n
    prev = -f_inf
    for i in range(n):
        if prev < T[i]:
            pattern[i] = 1
            prev = T[i]

    prev = -f_inf
    for i in reversed(range(n)):
        if prev < A[i]:
            if pattern[i] != 0 and T[i] != A[i]:
                print(0)
                exit()
            pattern[i] = 1
            prev = A[i]
        else:
            if pattern[i] != 0 and T[i] > A[i]:
                print(0)
                exit()

    res = 1
    for i in range(n):
        if pattern[i] == 0:
            pattern[i] = min(T[i], A[i])
        res = res * pattern[i] % mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

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

    # 左からみていく
    ans = 1
    for i in range(1, N - 1):
        if T[i - 1] < T[i] and A[i] > A[i + 1]:
            if T[i] == A[i]:
                continue
            else:
                print(0)
                return
        elif A[i] > A[i + 1]:
            if A[i] > T[i]:
                print(0)
                return
        elif T[i - 1] < T[i]:
            if T[i] > A[i]:
                print(0)
                return
        else:
            m = min(A[i], T[i])
            ans *= m
            ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def main():
    n = int(input())
    t = list(map(int, input().split()))
    a = list(map(int, input().split()))
    h = [None]*n
    h[0] = t[0]
    for i in range(1, n):
        if t[i-1] < t[i]:
            h[i] = t[i]
    f = True
    if h[n-1] is not None and h[n-1] != a[n-1]:
        f = False
    if h[n-1] is None:
        h[n-1] = a[n-1]
    for i in reversed(range(n-1)):
        if a[i] > a[i+1]:
            if h[i] is None:
                h[i] = a[i]
            else:
                if h[i] != a[i]:
                    f = False
        if h[i] is not None and h[i] > a[i]:
            f = False
    if f:
        ans = 1
        for i in range(n):
            if h[i] is None:
                ans *= min(t[i], a[i])
                ans %= MOD
        print(ans % MOD)
    else:
        print(0)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
T=list(map(int, input().split()))
A=list(map(int, input().split()))
H1,H2=[0]*N,[0]*N
h=0
for i in range(N):
  if h<T[i]:
    H1[i]=T[i]
    h=T[i]
h=0
for i in range(N):
  if h<A[-1-i]:
    H2[-1-i]=A[-1-i]
    h=A[-1-i]
#print(H1,H2)
H=[0]*N
for i in range(N):
  if H1[i]!=0 and H2[i]!=0 and H1[i]!=H2[i]:
    print(0)
    exit()
  else:
    H[i]=max(H1[i],H2[i])
    
if H1.index(max(H1))>H2.index(max(H2)):
  print(0)
  exit()
  
ans=1
left=H[0]
right=0
cnt=0
for i in range(1,N):
  if H[i]!=0 and cnt==0:
    left=H[i]
  elif H[i]!=0:
    right=H[i]
    d=min(left,right)
    ans*=pow(d,cnt,10**9+7)
    ans%=10**9+7
    cnt=0
    left=H[i]
  elif H[i]==0:
    cnt+=1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if n==1:
    print(int(a==b))
    exit()
mod=10**9+7
INF=10**9+1 
u=[INF]*n
d=[1]*n
u[0]=a[0]
d[0]=a[0]
for i in range(1,n):
    if a[i]-a[i-1]:
        d[i]=a[i]
    u[i]=a[i]
u[-1]=b[-1]
d[-1]=b[-1]
for i in range(n-2,-1,-1):
    if b[i]-b[i+1]:
        if b[i]<d[i] or b[i]>u[i]:
            print(0)
            exit()
        d[i]=b[i]
    u[i]=min(b[i],u[i])
ans=1
for i in range(n):
    ans=ans*(u[i]-d[i]+1)%mod
print(ans)

Submission status: Accepted

Solution code:
#2,3
#3,4

def main():
    N = int(input())
    A = [int(_n) for _n in input().split()]
    B = [int(_n) for _n in input().split()]
    max_h = [10**10]*N
    min_h = [1]*N
    prev = -1
    for i in range(N):
        a = A[i]
        if prev != a:
            max_h[i] = a
            min_h[i] = a
        else:
            max_h[i] = max_h[i-1]
            min_h[i] = 0
        prev = a
    prev = -1
    res = 1
    MOD = 10**9+7
    for i in reversed(range(N)):
        a = B[i]
        new_range = [0,0]
        if prev != a:
            new_range[0] = a
            new_range[1] = a
        else:
            new_range[0] = max_h[i+1]
            new_range[1] = 1
        if max_h[i] < new_range[1] or min_h[i] > new_range[0]:
            print(0)
            return
        max_h[i] = min(max_h[i], new_range[0])
        min_h[i] = max(min_h[i], new_range[1])
        # print(max_h[i],min_h[i])
        res = (max_h[i]-min_h[i]+1) * res % MOD
        prev = a
    print(res)



main()

Submission status: Accepted

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

arr = [[1, INF] for _ in range(n)]
cur_max = -1
for i in range(n):
    cur = t[i]
    if cur > cur_max:
        arr[i][0] = max(cur, arr[i][0])
        arr[i][1] = min(cur, arr[i][1])
        cur_max = cur
    else:
        arr[i][1] = min(cur, arr[i][1])

cur_max = -1
for i in reversed(range(n)):
    cur = a[i]
    if cur > cur_max:
        arr[i][0] = max(cur, arr[i][0])
        arr[i][1] = min(cur, arr[i][1])
        cur_max = cur
    else:
        arr[i][1] = min(cur, arr[i][1])

for i in range(n):
    if arr[i][0] > arr[i][1]:
        print(0)
        exit()

ans = 1
for i in range(n):
    ans *= arr[i][1] - arr[i][0] + 1
    ans %= MOD
print(ans)