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:
mod = 10 ** 9 + 7

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

HT = [False] * N
for i in range(1, N):
    if T[i - 1] < T[i]:
        HT[i] = True
HT[0] = True

HA = [False] * N
for i in range(N - 1):
    if A[i] > A[i + 1]:
        HA[i] = True
HA[-1] = True

ans = 1
for i in range(N):
    if HT[i] and HA[i]:
        ans *= 1 if T[i] == A[i] else 0
    elif HT[i]:
        ans *= 1 if T[i] <= A[i] else 0
    elif HA[i]:
        ans *= 1 if T[i] >= A[i] else 0
    else:
        ans = (ans * min(T[i], A[i])) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

MOD = 10**9 + 7

N = int(input())
T = np.array(input().split(),dtype=np.int64)
A = np.array(input().split(),dtype=np.int64)

Tlower = T.copy()
Tlower[1:][T[1:]<=T[:-1]] = 1

A = A[::-1]
Alower = A.copy()
Alower[1:][A[1:]<=A[:-1]] = 1
A = A[::-1]; Alower = Alower[::-1]

lower = np.maximum(Alower,Tlower)
upper = np.minimum(A,T)
x = np.maximum(0,upper - lower + 1)

L = len(x); Lsq = int(L**.5+1)
x = np.resize(x,Lsq**2); x[L:] = 1; x = x.reshape((Lsq,Lsq))
for n in range(1,Lsq):
    x[:,n] *= x[:,n-1]; x[:,n] %= MOD
for n in range(1,Lsq):
    x[n] *= x[n-1,-1]; x[n] %= MOD
answer = x[-1,-1]
print(answer)

Submission status: Accepted

Solution code:
MOD=10**9+7
n=int(input())
la=list(map(int,input().split()))
lb=list(map(int,input().split()))
l=[[1,10**9] for i in range(n)]
tmp=0
for num,i in enumerate(la):
    if i>tmp:
        l[num][0]=i
        l[num][1]=i
    else :
        l[num][1]=i
    tmp=max(tmp,i)
tmp=0
ans=1
for i in range(n-1,-1,-1):
    if lb[i]<l[i][0]:
        print(0);exit()
    elif lb[i]>tmp:
        if lb[i]<=l[i][1]:ans*=1 
        else:print(0);exit()
    else:
        ans=ans*(min(lb[i],l[i][1])-l[i][0]+1)%MOD
    tmp=max(tmp,lb[i])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# code-festival-2016-qualcC - 二人のアルピニスト / Two Alpinists
def main():
    """
      /----\     <- x = y
     /      \--\
    /           \
      xi  yi
    0 ~ xi / xi ~ yi / yi+1 ~ N-1
    """
    N = int(input())
    T = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    x, y = T[-1], A[0]  # max of x, y
    xi, yi = T.index(x), N - A[::-1].index(y) - 1  # indices of x, y
    if x != y or xi > yi:  # corner case
        print(0)
        return
    MOD = 10 ** 9 + 7
    ans, cur = 1, 0
    for i in T[: xi + 1]:
        if i > cur:  # point of new altitude -> no choice (ans * 1)
            cur = i
        else:
            ans = (ans * cur) % MOD  # mulitple choices (1, 2, ..., cur)
    for _ in range(xi + 1, yi):
        ans = (ans * cur) % MOD
    for i in A[yi + 1 :]:
        if i < cur:
            cur = i
        else:
            ans = (ans * cur) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# code-festival-2016-qualcC - 二人のアルピニスト / Two Alpinists
from bisect import bisect_left as bs


def main():
    """
      /----\     <- xi (= yi)
     /      \--\
    /           \
      xi  yi
    0 ~ xi / xi ~ yi / yi+1 ~ N-1
    """
    N = int(input())
    T = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    x, y = T[-1], A[0]  # max of x, y
    xi, yi = T.index(x), N - A[::-1].index(y) - 1  # indices of x, y
    if x != y or xi > yi:
        print(0)
        return
    MOD = 10 ** 9 + 7
    ans, cur = 1, 0
    for i in T[: xi + 1]:
        if i > cur:  # point of new altitude -> no choice (ans * 1)
            cur = i
        else:
            ans = (ans * cur) % MOD  # mulitple choices (1, 2, ..., cur)
    for _ in range(xi + 1, yi):
        ans = (ans * cur) % MOD
    for i in A[yi + 1 :]:
        if i < cur:
            cur = i
        else:
            ans = (ans * cur) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# code-festival-2016-qualcC - 二人のアルピニスト / Two Alpinists
from bisect import bisect_left as bs


def main():
    """
      /----\     <- xi (= yi)
     /      \--\
    /           \
      xi  yi
    0 ~ xi / xi ~ yi / yi+1 ~ N-1
    """
    N = int(input())
    T = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    x, y, xi, yi = 0, 0, 0, 0  # max of x, y and the indices
    for i, t in enumerate(T):
        if t > x:
            x, xi = t, i
    for i, a in enumerate(A):
        if a >= y:
            y, yi = a, i
    if x != y or xi > yi:
        print(0)
        return
    MOD = 10 ** 9 + 7
    ans, cur = 1, 0
    for i in T[: xi + 1]:
        if i > cur:  # point of new altitude -> no choice (ans * 1)
            cur = i
        else:
            ans = (ans * cur) % MOD  # mulitple choices (1, 2, ..., cur)
    for _ in range(xi + 1, yi):
        ans = (ans * cur) % MOD
    for i in A[yi + 1 :]:
        if i < cur:
            cur = i
        else:
            ans = (ans * cur) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
T = [0]+list(map(int,input().split()))+[float('inf')]
A = [float('inf')]+list(map(int,input().split()))+[0]
ans = 1
MOD = 10**9+7
for i in range(1,N+1):
    if T[i-1] < T[i]:
        ans *= int(T[i] <= A[i])
    if A[i] > A[i+1]:
        ans *= int(T[i] >= A[i])
    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())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
MOD = 10**9 + 7

def restor_accumulation_max(accumulation_max: list, include_0: bool) -> list:
    '''累積Maxを復元する
    Maxには逆元が存在しないので、一意に復元することはできない
    復元値の候補を[begin, end)として定義される
 
    例: accumulation_max = [3, 4, 4, 8, 8]
        include_0 = Trueのとき
        -> [(3, 4), (4, 5), (0, 5), (8, 9), (0, 9)]
        include_0 = Falseのとき
        -> [(3, 4), (4, 5), (0, 5), (8, 9), (1, 9)]
    '''
    n = len(accumulation_max)
    res = []
    init = 0 if include_0 else 1
    max_ = init
    
    for i in range(n):
        if accumulation_max[i] > max_:
            res.append((accumulation_max[i], accumulation_max[i] + 1))
            max_ = accumulation_max[i]
        else:
            res.append((init, max_ + 1))
    
    return res

li_t = restor_accumulation_max(t, False)
li_a = restor_accumulation_max(a[::-1], False)[::-1]

ans = 1
for i in range(n):
    tmp = min(li_t[i][1], li_a[i][1]) - max(li_t[i][0], li_a[i][0])
    if tmp <= 0:
        ans *= 0
    ans *= tmp
    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

li_t = []
max_t = 0
for i in range(n):
    if t[i] > max_t:
        li_t.append((t[i], t[i] + 1))
        max_t = t[i]
    else:
        li_t.append((1, max_t + 1))

li_a = []
max_a = 0
for i in range(n)[::-1]:
    if a[i] > max_a:
        li_a.append((a[i], a[i] + 1))
        max_a = a[i]
    else:
        li_a.append((1, max_a + 1))
li_a = li_a[::-1]

ans = 1
for i in range(n):
    tmp = min(li_t[i][1], li_a[i][1]) - max(li_t[i][0], li_a[i][0])
    if tmp <= 0:
        ans *= 0
    ans *= tmp
    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
if N == 1:
    if T[0] == A[0]:
        print(1)
    else:
        print(0)
    exit()

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

Submission status: Accepted

Solution code:
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)
elif n == 2:
    if t[0] >= a[1]:
        if t[0] == t[1] and a[0] >= a[1]:
            if t[0] == a[0]:
                print(1)
            else:
                print(0)
        else:
            print(0)
    else:
        if t[0] < t[1] and a[0] == a[1] and a[1] == t[1]:
            print(1)
        else:
            print(0)
else:
    mod = 10**9 + 7
    ans = 1
    for i in range(1,n-1):
        if t[i-1] == t[i]:
            if a[i+1] == a[i]:
                ans = (ans*(min((a[i],t[i]))%mod)) % mod
            else:
                if a[i] > t[i]:
                    ans = 0
                    break
        else:
            if a[i] < t[i]:
                ans = 0
                break
    if t[0] > a[0] or t[n-1] < a[n-1]:
        ans = 0
    print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

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

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

    minHeight = [float('inf')] * N
    minHeight[0] = -1
    minHeight[N - 1] = -1

    for i in range(1, N - 1):
        if T[i] > T[i - 1]:
            if T[i] > A[i]:
                print(0)
                return
            minHeight[i] = -1
        if A[i] > A[i + 1]:
            if A[i] > T[i]:
                print(0)
                return
            minHeight[i] = -1
        minHeight[i] = min(minHeight[i], A[i], T[i])

    ans = 1
    for h in minHeight:
        if h == -1:
            continue
        ans = (ans * h) % MOD

    print(ans)

sol()

Submission status: Accepted

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

m=[a[i] for i in range(1,n+1)]
l=[1 for _ in range(n)]

for i in range(n):
	if a[i]<a[i+1]:
		l[i]=a[i+1]
		
ans=1
for i in range(n-1,-1,-1):
	if b[i+1]<b[i]:
		if l[i]>b[i]:
			ans=0
		else:
			l[i]=b[i]
	m[i]=min(m[i],b[i])
	
for i in range(n):
	ans=(ans*(m[i]-l[i]+1))%(10**9+7)
	if m[i]<l[i]:
		ans=0
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
T,A=[list(map(int,input().split())) for i in range(2)]
tp,ap=0,A[0]
f=0
r=1
mod=10**9+7
x=0
if T[-1]!=A[0]:
    f=-1
for t,a in zip(T,A):
    if f==-1:
        break
    if f==0:
        if t==tp and a==ap:
            r=(r*t)%mod
        elif t==a==ap:
            f=1
        elif not (t>tp and a==ap):
            f=-1
    elif f==1:
        if t==a==ap:
            x+=1
        elif t==tp and a<ap:
            for j in range(x-1):
                r=(r*t)%mod
            f=2
        else:
            f=-1
    elif f==2:
        if t==tp and a==ap:
            r=(r*a)%mod
        elif not (t==tp and a<ap):
            f=-1
    tp,ap=t,a
if f==1:
    for j in range(x-1):
        r=(r*t)%mod
print(0 if f<1 else r)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

def main():
  n=I()

  a=LI()
  b=LI()

  if n==1 and a[0]!=b[0]:
    return 0

  l1=[]
  l2=[]

  amx=a[0]
  l1.append(1)
  for i in range(1,len(a)):
    x=a[i]
    if amx<x:
      # 矛盾
      if x>b[i]:
        print(0)
        exit()

      l1.append(1)
      amx=x
    elif amx==x:
      l1.append(amx)
    else:
      print(0)
      exit()

  b.reverse()
  l1.reverse()

  bmx=b[0]
  l2.append(1)
  for i in range(1,len(b)):
    x=b[i]
    if bmx<x:
      # 矛盾
      if x>a[n-i-1]:
        print(0)
        exit()

      l2.append(1)
      bmx=x
    elif bmx==x:
      l2.append(min(bmx,l1[i]))
    else:
      print(0)
      exit()

  ans=1
  for x in l2:
    ans*=x
    ans%=mod

  return ans

print(main())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    n = I()

    return

#C
def C():
    n = I()
    t = LI()
    a = LI()
    f = [1]*n
    h = [float("inf")]*n
    ma = 0
    for i in range(n):
        if t[i] > ma:
            ma = t[i]
            f[i] = 0
        h[i] = ma
    ma = 0
    for i in range(n)[::-1]:
        if a[i] > ma:
            ma = a[i]
            if not f[i] and h[i] != ma:
                print(0)
                return
            f[i] = 0
            if h[i] < ma:
                print(0)
                return
        if ma < h[i]:
            h[i] = ma
    ans = 1
    for i in range(n):
        if f[i]:
            ans *= h[i]
            ans %= mod
    print(ans)
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

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
M = list(map(min,zip(A,T)))[1:-1]
m = [max(T[i] if T[i]>T[i-1] else 1, A[i] if A[i]>A[i+1] else 1) for i in range(1,N+1)]
ans = 1
for a,b in zip(m,M): ans = ans * max(0,b-a+1) % mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
*T, = map(int,input().split())
*A, = map(int,input().split())

mod = 10**9+7
mT = [T[0]]*N
MT = [T[0]]*N
for i,t in enumerate(T[1:],1):
    if t>T[i-1]:
        mT[i] = t
        MT[i] = t
    else:
        mT[i] = 1
        MT[i] = t
mA = [A[-1]]*N
MA = [A[-1]]*N
for i,a in enumerate(A[-2::-1],2):
    if a>A[-i+1]:
        mA[-i] = a
        MA[-i] = a
    else:
        mA[-i] = 1
        MA[-i] = a
m = [max(a,t) for a,t in zip(mA,mT)]
M = [min(a,t) for a,t in zip(MA,MT)]
ans = 1
for a,b in zip(m,M):
    ans *= max(0,b-a+1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = int(1e9) + 7


def calc(N, T, A):
    highest = max(T)
    if highest != max(A):
        return 0
    l = T.index(highest)
    r = A.index(highest)
    if N - (l + r) <= 0:
        return 0
    elif N - (l + r) == 1:
        ans = 1
    else:
        free = N - (l + r) - 2
        ans = pow(highest, free, MOD)
    prev = 0
    for i in range(l):
        if T[i] == prev:
            ans = (ans * T[i]) % MOD
        prev = T[i]
    prev = 0
    for i in range(r):
        if A[i] == prev:
            ans = (ans * A[i]) % MOD
        prev = A[i]
    return ans


def main():
    N = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))[::-1]
    ans = calc(N, T, A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
a=[-1]*n
b=[-1]*n
c=[-1]*n
s=arr1[0]
a[0]=s
for i in range(n):
  if arr1[i]==1:
    a[i]=1
  else:
    if s!=arr1[i]:
      a[i]=arr1[i]
      s=arr1[i]
s=arr2[-1]
b[-1]=s
for i in range(1,n+1):
  if arr2[-i]==1:
    b[-i]=1
  else:
    if s!=arr2[-i]:
      b[-i]=arr2[-i]
      s=arr2[-i]
flag=False
for i in range(n):
  if a[i]==-1 and b[i]==-1:
    c[i]=-1
  elif a[i]==-1:
    if arr1[i]>=b[i]:
      c[i]=b[i]
    else:
      flag=True
  elif b[i]==-1:
    if arr2[i]>=a[i]:
      c[i]=a[i]
    else:
      flag=True
  else:
    if a[i]==b[i]:
      c[i]=a[i]
    else:
      flag=True
if flag==True:
  print(0)
else:
  l=0
  r=0
  ans=1
  cnt=0
  for i in range(n):
    if c[i]==-1:
      if cnt==0:
        l=c[i-1]
      cnt+=1
    else:
      if cnt!=0:
        r=c[i]
        for _ in range(cnt):
          ans=(ans*min(l,r))%mod
        cnt=0
  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], 1]]
Y = [[A[N-1], 1]]

for i in range(1,N) :
    pv,pf = X[i-1]
    nv = T[i]
    
    if nv == 1 :
        X.append([nv, 1])
    elif pv >= nv :
        X.append([nv, 0])
    else :
        X.append([nv, 1])
    
    pv,pf = Y[i-1]
    nv = A[N-1-i]
    
    if nv == 1 :
        Y.append([nv, 1])
    elif pv >= nv :
        Y.append([nv, 0])
    else :
        Y.append([nv, 1])

Y = Y[::-1]

ans = 1

mat = 0
maa = 0

for i in range(N) :
    tv,tf = X[i]
    av,af = Y[i]
    
    mat = max(mat, tv)
    maa = max(maa, av)
    
    if tf == 1 and af == 0 :
        if tv > maa :
            ans = 0
            break
    elif tf == 0 and af == 1 :
        if av > mat :
            ans = 0
            break
    elif tf == 1 and af == 1 :
        if tv != av :
            ans = 0
            break
    else :
        ans *= min(tv,av)
        ans %= (10**9+7)
        
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

count=0
for i in range(N):
    if A[i]==T[N-1] and T[i]==T[N-1]:
        count+=1


if count==0:
    print(0)
else:
    count=max(0,count-2)

    mod = 10**9+7
    d = pow(T[N-1],count,mod)

    from collections import Counter

    tc=Counter(T)

    for key in tc.keys():
        if key!=T[N-1]:
            d*=pow(key,tc[key]-1,mod)
            d%=mod

    ac=Counter(A)

    for key in ac.keys():
        if key!=T[N-1]:
            d*=pow(key,ac[key]-1,mod)
            d%=mod

    print(d)

Submission status: Accepted

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

t = [0]+t+[t[-1]]
a = [a[0]]+a+[0]

ans = 1

for i in range(1,n+1):
    if t[i]==t[i-1] and a[i]==a[i+1]:
        ans *= min(t[i],a[i])
        ans %= 10**9+7
    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 t[i]>a[i]:
        print(0)
        exit()
    elif a[i]!=a[i+1] and a[i]>t[i]:
        print(0)
        exit()

print(ans)

Submission status: Accepted

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
max_T = max(T)
max_A = max(A)
if max_A != max_T:
    print(0)
    exit()
mt,ma = 0,0
ans = 1
for i in range(N):
    if T[i] == max_T:

        break
    else:
        if T[i] > mt:
            mt = T[i]
        else:
            ans *= mt
            ans %= mod
for j in range(N)[::-1]:
    if A[j] == max_A:
        break
    else:
        if A[j] > ma:
            ma = A[j]
        else:
            ans *= ma
            ans %= mod
if i == j:
    print(ans)
    exit()
elif j < i:
    print(0)
    exit()
else:
    ans *= pow(max_A,j-i-1,mod)
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

N = int(input())
T = inpl()
A = inpl()

OK = True
D = [0]*N
D[0] = 1

for i in range(1, N):
    if T[i-1] < T[i]:
        D[i] = 1

if D[-1] and (A[-1] != T[-1]):
    OK = False
else:
    D[-1] = 1

for i in range(N-2, -1, -1):
    if A[i] > A[i+1]:
        if D[i] and (A[i] != T[i]):
            OK = False
        else:
            if A[i] > T[i]:
                OK = False
            D[i] = 1

ans = OK
MOD = 10**9 + 7
for i in range(N):
    if D[i] == 0:
        ans = ans * min(A[i], T[i]) % MOD
print(ans*1)

Submission status: Accepted

Solution code:
# CODE FESTIVAL 2016 qual C C - 二人のアルピニスト / Two Alpinists
N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
T = [0] + T + [T[-1]]
A = [A[0]] + A + [0]

K = [0 for k in range(N+2)]
L = [0 for k in range(N+2)]
for k in range(1,N+2):
    if T[k-1] != T[k]:
        K[k] = T[k]
for k in range(1,N+2):
    if A[N-k+2] != A[N-k+1]:
        L[N-k+1] = A[N-k+1]

MOD = 10**9 + 7
ans = 1
for k in range(1,N+1):
    if K[k] == L[k] == 0:
        ans *= min(A[k],T[k])
        ans %= MOD
    elif (K[k]>0 and A[k]<K[k]) or (L[k]>0 and T[k]<L[k]):
        print(0)
        exit(0)
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n = int(input())
t = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

height = [0] * n
height[0] = t[0]
for i in range(1, n):
    if t[i] > t[i-1]:
        height[i] = t[i]
        if t[i] > a[i]:
            print(0)
            exit()
if height[-1] == 0:
    height[-1] = a[-1]
elif height[-1] != a[-1]:
        print(0)
        exit()

for i in range(n-1, 0, -1):
    if a[i] < a[i-1]:
        if height[i-1] == 0:
            height[i-1] = a[i-1]
            if a[i-1] > t[i-1]:
                print(0)
                exit()
        elif height[i-1] != a[i-1]:
            print(0)
            exit()

ans = 1
for i, item in enumerate(height):
    if item == 0:
        ans *= min(t[i], a[i])
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - 二人のアルピニスト / Two Alpinists
https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_c

"""
import sys


def solve(N, T, A):
    mountains_t = dict()
    peak_t = T[0]
    mountains_t[1] = (peak_t, peak_t)
    for i, t in enumerate(T[1:], start=2):
        if t > peak_t:
            peak_t = t
            mountains_t[i] = (peak_t, peak_t)
        else:
            if t < peak_t:
                return 0
            mountains_t[i] = (1, peak_t)

    mountains_a = dict()
    peak_a = A[-1]
    mountains_a[N] = (peak_a, peak_a)
    for j, a in zip(range(N-1, 0, -1), reversed(A[:-1])):
        if a > peak_a:
            peak_a = a
            mountains_a[j] = (peak_a, peak_a)
        else:
            if a < peak_a:
                return 0
            mountains_a[j] = (1, peak_a)

    MOD = 10**9 + 7
    ans = 1
    for i in range(1, N+1):
        lt, ht = mountains_t[i]
        la, ha = mountains_a[i]
        if lt == ht or la == ha:
            if lt == ht and la == ha:
                if lt != la:
                    return 0
            elif lt == ht:
                if not la <= lt <= ha:
                    return 0
            else:
                if not lt <= la <= ht:
                    return 0
        else:
            high = min(ht, ha)
            ans = ans * high% MOD
    return ans


def main(args):
    N = int(input())
    T = [int(t) for t in input().split()]
    A = [int(a) for a in input().split()]
    ans = solve(N, T, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=[0,T[0]]
Ares[-1]=[0,A[-1]]
for i in range(1,n):
  if T[i]>T[i-1]:
    Tres[i]=[0,T[i]]
  else:
    Tres[i]=[1,T[i]]
  if A[-i-1]>A[-i]:
    Ares[-i-1]=[0,A[-i-1]]
  else:
    Ares[-i-1]=[1,A[-i-1]]
ans=1
for i in range(n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==1 and aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]>Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]>Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
if Tres[0]<=Ares[0]:
  ans=1
else:
  ans=0
for i in range(1,n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%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
Tres=[0]*N
Ares=[0]*N
Tres[0]=(0,T[0])
Ares[N-1]=(0,A[N-1])
for i in range(1,N):
    if T[i]>Tres[i-1][1]:
        Tres[i]=(0,T[i])
    else:
        Tres[i]=(1,T[i])
    if A[N-i-1]>Ares[N-i][1]:
        Ares[N-i-1]=(0,A[N-i-1])
    else:
        Ares[N-i-1]=(1,A[N-i-1])
if Tres[0]<=Ares[0]:
    ans=1
else:
    ans=0
for i in range(1,N):
    x,t=Tres[i]
    y,a=Ares[i]
    if x==y==1:
        ans=ans*min(t,a)%mod
    elif x==1 and y==0 and t<a:
        ans=0
    elif x==0 and y==1 and t>a:
        ans=0
    elif x==0 and y==0 and t!=a:
        ans=0
print(ans)

Submission status: Accepted

Solution code:
import sys
mod = 10**9 + 7

def nai():
    print(0)
    sys.exit()

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

M = max(A)
if M != max(T):
    nai()

iT = T.index(M)
iA = N - 1 - A[::-1].index(M)
if iA < iT:
    nai()
ans = pow(M, max(0, iA - iT - 1), mod)
pre = -1
for t in T[:iT]:
    if pre == t:
        ans = t*ans%mod
    pre = t
pre = -1
for a in A[::-1]:
    if a == M:
        break
    if pre == a:
        ans = a*ans%mod
    pre = a
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
T=list(map(int,input().split()))
t=[1]
for i in range(1,N):
    if T[i]!=T[i-1]:
        t.append(1)
    else:
        t.append(T[i])
    if T[i]<T[i-1]:
        print(0)
        exit()
A=list(map(int,input().split()))
A=A[::-1]
a=[1]
for i in range(1,N):
    if A[i]!=A[i-1]:
        a.append(1)
    else:
        a.append(A[i])
    if A[i]<A[i-1]:
        print(0)
        exit()
A=A[::-1]
a=a[::-1]
#print(t)
#print(a)
M=max(A)

for i in range(N):
    if T[i]==M:
        if A[i]==M:
            break
        else:
            print(0)
            exit()

for i in range(N):
    if A[N-1-i]==M:
        if T[N-1-i]==M:
            break
        else:
            print(0)
            exit()
ans=1
mod=(10**9+7)
for i in range(N):
    ans*=min(t[i],a[i])
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007
n = int(input())
tli = [ int(it) for it in input().split() ]
ali = [ int(it) for it in input().split() ]
#print (tli,ali)

mav1 = max(tli)
mav2 = max(ali)
mav = mav1
#print (mav1,mav2)
if (mav1!=mav2):
  print (0)
else:
  mai1 = tli.index(mav)
  mai2 = n-1-list(reversed(ali)).index(mav)
  #print (mai1,mai2)
  if (mai2<mai1):
    print (0)
  else:
    s = 1
    tma = -1
    for i in range(0,mai1+1):
      if tli[i]>tma:
        tma = tli[i]
        #print ("lt",tma)
      else:
        s*=(tli[i])
        s%=MOD
        #print ("l")
    tma = -1
    for i in range(n-1,mai2-1,-1):
      if ali[i]>tma:
        tma = ali[i]
        #print ("rt",tma)
      else:
        s*=(ali[i])
        s%=MOD
        #print ("r")
    if (mai2-mai1>1):
      for i in range(mai2-mai1-1):
        s*=mav
        s%=MOD
    print ( s%(1000000007) )

Submission status: Accepted

Solution code:
#CODEFESTIVAL2016qualC
N=int(input())
mod=10**9+7
T=list(map(int,input().split()))
A=list(map(int,input().split()))
ansT=[0]*N
ansA=[0]*N
ansT[0]=-1*T[0]
ansA[N-1]=-1*A[N-1]
for i in range(1,N):
    if T[i]>T[i-1]:
        ansT[i]=-1*T[i]
    else:
        ansT[i]=T[i]
    if A[N-1-i]>A[N-i]:
        ansA[N-1-i]=-1*A[N-1-i]
    else:
        ansA[N-1-i]=A[N-1-i]
ans=1
for i in range(N):
    if ansT[i]<0 and ansA[i]<0 and ansT[i]!=ansA[i]:
        ans=0
        break
    elif ansT[i]>0 and ansA[i]>0:
        ans=(ans*min(ansT[i],ansA[i]))%mod
    elif ansT[i]<0 and ansA[i]>0 and abs(ansT[i])>ansA[i]:
        ans=0
        break
    elif ansT[i]>0 and ansA[i]<0 and abs(ansA[i])>ansT[i]:
        ans=0
        break
print(ans)