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: Runtime Error

Solution code:
N = int(raw_input())

T = map(int, raw_input().split())
A = map(int, raw_input().split())

ans = 1
mod = 10 ** 9 + 7

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

for i in xrange(N):
    if i == 0 or i == n - 1:
        continue
    elif T[i] > T[i-1]:
        if A[i] < T[i] and A[i] == A[i + 1]:
            print 0
            exit()
        elif A[i] != T[i] and A[i] != A[i + 1]:
            print 0
            exit()
    else:
        if T[i] == A[i]:
            if A[i] == A[i + 1]:
                ans *= T[i]
        elif T[i] > A[i]:
            if A[i] == A[i + 1]:
                ans *= A[i]
        else:
            if A[i] == A[i + 1]:
                ans *= T[i]
            else:
                print 0
                exit()

print ans % mod

Submission status: Runtime Error

Solution code:
N = int(raw_input())

T = map(int, raw_input().split())
A = map(int, raw_input().split())

ans = 1
mod = 10 ** 9 + 7

if T[n - 1] != A[0]:
    ans = 0

else:
    for i in xrange(1, N - 1):
        if T[i] > A[i]:
            ans = (ans * A[i]) % mod
        elif T[i] < A[i]:
            ans = (ans * T[i]) % mod

print ans % mod

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(raw_input())
T = map(int, raw_input().split())
A = map(int, raw_input().split())
T = np.array(T)
A = np.array(A)

arr = np.ones((len(A),))
res = 1
rest = np.zeros((len(A),))

if max(A) != max(T):
    res = 0
else:
    for t in range(T.shape[0]):
        if t > 0 and T[t] == T[t-1] and t != T.shape[0]-1:
            arr[t] = T[t]
        elif t != T.shape[0]-1:
            rest[t] = T[t]
    for a in range(A.shape[0])[::-1]:
        if rest[a]>1 and A[a]<rest[a]:
            arr = np.zeros((len(A),))
            break
        elif a < A.shape[0]-1 and a != 0 and arr[a] != 1:
            if A[a] > A[a+1]:
                arr[a] = 1
            elif A[a] < arr[a]:
                arr[a] = A[a]
    for j in arr:
        res *= j

if res != 0:
    res = res % ((10**9) + 7)

print int(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N = int(raw_input())
T = map(int, raw_input().split())
A = map(int, raw_input().split())
T = np.array(T)
A = np.array(A)

arr = np.ones((len(A),))
res = 1
rest = np.zeros((len(A),))

if max(A) != max(T):
    res = 0
else:
    for t in range(T.shape[0]):
        if t > 0 and T[t] == T[t-1] and t != T.shape[0]-1:
            arr[t] = T[t]
        elif t != T.shape[0]-1:
            rest[t] = T[t]
    for a in range(A.shape[0])[::-1]:
        if rest[a]>1 and A[a]<rest[a]:
            arr = np.zeros((len(A),))
            break
        elif a < A.shape[0]-1 and a != 0 and arr[a] != 1:
            if A[a] > A[a+1]:
                arr[a] = 1
            elif A[a] < arr[a]:
                arr[a] = A[a]
    for j in arr:
        res *= j

if res != 0:
    res = res % ((10**9) + 7)

print int(res)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
t=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
a_max=max(a)
t_max=max(t)
if a_max != t_max(t):
    print(0)
    sys.exit()
i=0
sum=1
while t[i]!=t_max:
    if t[i]==t[i+1]:
        sum*=t[i]
j=len(a)-1
while a[j]!=a_max:
    if a[j]==a[j-1]:
        sum*=a[j]
sum=sum*(a_max**(n-(i+j+1)))%((1e+9)+7)
print(int(sum))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

n = stdin.readline()
n = n.strip().split(" ")
N = int(n[0])
n = stdin.readline()
n = n.strip().split(" ")
T = []
for t in n:
    T.append(int(t))
T = np.array(T)
n = stdin.readline()
n = n.strip().split(" ")
A = []
for a in n:
    A.append(int(a))
A = np.array(A)

arr = np.ones((len(A),))
res = 1
rest = np.zeros((len(A),))

if max(A) != max(T):
    res = 0
else:
    for t in range(T.shape[0]):
        if t > 0 and T[t] == T[t-1] and t != T.shape[0]-1:
            arr[t] = T[t]
        elif t != T.shape[0]-1:
            rest[t] = T[t]
    for a in range(A.shape[0])[::-1]:
        if rest[a]>1 and A[a]<rest[a]:
            arr = np.zeros((len(A),))
            break
        elif a < A.shape[0]-1 and a != 0 and arr[a] != 1:
            if A[a] > A[a+1]:
                arr[a] = 1
            elif A[a] < arr[a]:
                arr[a] = A[a]
    for j in arr:
        res *= j

if res != 0:
    res = res % ((10**9) + 7)
    
print int(res)

Submission status: Runtime Error

Solution code:
def read():
	return [int(i) for i in input().split(" ")]
N = int(input())
T = read()
A = read()
tempT, tempA = 0, 0
for i in range(N):
	if(T[i] > tempT):
		tempT = L[i] = T[i]
		L.append(tempT)
		unknowL.append(0)
	else:
		unknowL.append(T[i])
		L.append(0)
for i in range(N):
	val = A.pop()
	if(A[i] > tempA):
		if(L[i] != 0 and L[i] != val):
			print(0)
			exit()
		tempA = L[i] = val 
		unknowL[i] = 0
	else:
		unknowL[i] = min(unknowL[i], val)
P = 1 
for i in unknowL:
	if(i != 0):
		P *= i	
print(P % (10**9 +7))

Submission status: Runtime Error

Solution code:
def read():
	return [int(i) for i in input().split(" ")]
N = int(input())
T = read()
A = read()
tempT, tempA = 0, 0
for i in range(N):
	if(T[i] > tempT):
		tempT = L[i] = T[i]
		L.append(tempT)
		unknowL.append(0)
	else:
		unknowL.append(T[i])
		L.append(0)
for i in range(N-1, -1, -1):
	if(A[i] > tempA):
		if(L[i] != 0 and L[i] != A[i]):
			print(0)
			exit()
		tempA = L[i] = A[i]
		unknowL[i] = 0
	else:
		unknowL[i] = min(unknowL[i], A[i])
P = 1 
for i in unknowL:
	if(i != 0):
		P *= i	
print(P % (10**9 +7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

n = stdin.readline()
n = n.strip().split(" ")
N = int(n[0])
n = stdin.readline()
n = n.strip().split(" ")
T = []
for t in n:
	T.append(int(t))
T = np.array(T)
n = stdin.readline()
n = n.strip().split(" ")
A = []
for a in n:
	A.append(int(a))
A = np.array(A)

arr = np.ones((len(A),))
res = 1
rest = np.zeros((len(A),))


if max(A) != max(T):
	res = 0
else:
	for t in range(T.shape[0]):
		if t > 0 and T[t] == T[t-1] and t != T.shape[0]-1:
			arr[t] = T[t]
		elif t != T.shape[0]-1:
			rest[t] = T[t]
	for a in range(A.shape[0])[::-1]:
		if rest[a]>1 and A[a]<rest[a]:
			arr = np.zeros((len(A),))
			break
		elif a < A.shape[0]-1 and a != 0 and arr[a] != 1:
			if A[a] > A[a+1]:
				arr[a] = 1
			elif A[a] < arr[a]:
				arr[a] = A[a]
	for j in arr:
		res *= j

if res != 0:
	res = res % ((10**9) + 7)
print int(res)

Submission status: Runtime Error

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

Z = []
for i in range(N):
        Z.append(min(T[i],A[i]))

sum = 1
offset = []
if max(Z) < max(T(-1),A(0)):
        print(0)
else:
        for i in range(1,N-1):
                if not (Z[i] > Z[i-1] or Z[i] > Z[i+1]):
                        offset.append(i)
        for j in offset:
                sum *= Z[j]
        print(sum%(1000000000 + 7))

Submission status: Runtime Error

Solution code:
import math as mt

import operator as op
def ncr(n, r):
    r = min(r, n-r)
    if r == 0: return 1
    numer = reduce(op.mul, xrange(n, n-r, -1))
    denom = reduce(op.mul, xrange(1, r+1))
    return numer//denom

N = input()
T = map(lambda x:int(x), raw_input().split())
A = map(lambda x:int(x), raw_input().split())

check = [False for x in range(N)]
check[0] = True
check[N - 1] = True

ans = N - 2
n = max(T)

for i in range(1, len(T) - 1):
    if T[i - 1] < T[i]:
        global LastT = T[i]
        check[i] = True
    if A[i + 1] < A[i]:
        global LastA = A[i]
        check[i] = True

if max(T) != max(A):
    print 0
else:
    if (((N % (10 ** 9 + 7) - sum(check) % (10 ** 9 + 7)) % (10 ** 9 + 7)) ** 2) % (10 ** 9 + 7) == 0:
        print 1
    else:
        print (((N % (10 ** 9 + 7) - sum(check) % (10 ** 9 + 7)) % (10 ** 9 + 7)) ** 2) % (10 ** 9 + 7)
    #print ncr((n % (10 ** 9 + 7) - (N % (10 ** 9 + 7) - sum(check) % (10 ** 9 + 7))) % (10 ** 9 + 7), ((N - sum(check)) % (10 ** 9 + 7)))

Submission status: Runtime Error

Solution code:
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
h = [0 for i in range(N)]
if T[-1] != A[0]:
	print(0)
	exit()
else:
	h[0] = T[0]
	h[-1] = A[-1]
	for i in range(1,N):
		if T[i] > T[i-1]:
			if T[i] < h[i]:
				print(0)
				exit()
			else:
				h[i] = T[i]
		else:
			if h[i] < 0:
				h[i] = max(h[i],-T[i])
			elif T[i] < h[i]:
				print(0)
				exit()
			elif h[i] == 0:
				h[i] = -T[i]
		if A[-i-1] > A[-i]:
			if A[-i-1] < h[-i-1]:
				print(0)
				exit()
			exit()
				h[-i-1] = A[-i-1]
		else:
			if h[-i-1] < 0:
				h[-i-1] = max(h[-i-1],-A[-i-1])
			elif A[-i-1] < h[-i-1]:
				print(0)
				exit()
			elif h[-i-1] == 0:
				h[-i-1] = -A[-i-1]
a = 1
for n in h:
	if a > 10**9+7:
		a %= 10**9+7
	if n < -1:
		a *= -n
print(a%(10**9+7))

Submission status: Runtime Error

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


K, T = map(int, input().split())
hoge = list(map(int, input().split()))

a = [0]*T
for i in range(T):
	a[i] = (hoge[i], i)

if T == 1:
	print(K-1)
else:
	a.sort()
	a[-1] = (a[-1][0] - 1, a[-1][1])
	pre = a[-1][1]

	while True:
		a.sort()
		if a[-1][0] == 0:
			print(0)
			raise NameError('error')
			break
		elif a[-1][1] != pre:
			a[-1] = (a[-1][0] - 1, a[-1][1])
			pre = a[-1][1]
		else:
			if a[-2][0] == 0:
				print(a[-1][1])
				break
			else:
				a[-2] = (a[-2][0] - 1, a[-2][1])
				pre = a[-2][1]

Submission status: Runtime Error

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

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

ans=1
for i in xrange(n):
    if i==0 or i==n-1 or t[i]>t[i-1]:
        if a[i]<t[i] and a[i]==a[i+1]:
            print(0)
            exit()
        elif a[i]!=t[i] and a[i]!=a[i+1]:
            print(0)
            exit()
        continue
    else:
        if t[i]==a[i]:
            if a[i]==a[i+1]:
                ans=(ans*t[i])%mod
        elif t[i]>a[i]:
            if a[i]==a[i+1]:
                ans=(ans*a[i])%mod
        elif a[i]>t[i]:
            if a[i]==a[i+1]:
                ans=(ans*t[i])%mod
            else:
                print(0)
                exit()
print(ans%mod)

Submission status: Runtime Error

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

h = 0
for i in range(N):
    if h < T[i]:
        B[i] = T[i] h = T[i] 
h = 0
check = True
for i in range(N):
    if h < A[N-i-1]:
        if B[N-i-1] != 0 and B[N-i-1] != A[N-i-1]:
            check = False
        else:
            B[N-i-1] = A[N-i-1]
            h = A[N-i-1]

for i in range(N):
    if B[i] == 0:
        B[i] = min((T[i],A[i]))
    else:
        B[i] = 1

if check:
    ans = 1
    for i in range(N):
        ans = (ans * B[i]) % (int(1e9 + 7))
    print(ans)
else:
    print(0)

Submission status: Runtime Error

Solution code:
import sys
n = input()
t = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = 0
if max(t) != max(a):
    print ans
    sys.exit()
supermax = max(t)
flagt = 0
flaga = 0
for i in range(n):
    if flagt = 0 and t[i] == supermax:
        flagt = i
    if flaga = 0 and a[n-1-i] == supermax:
        flaga = n-1-i
if flagt > flaga:
    print ans
    sys.exit()


ans = 1
tmx = t[0]
amx = a[n-1]
if (n%2)==0:
    loop = n/2-1
else:
    loop = n/2
for i in range(loop):
    if t[i+1] <= a[i+1]:
        if t[i+1] == tmx:
            ans *= t[i+1]
    tmx = t[i+1]
    if a[(n-1)-(i+1)] <= t[(n-1)-(i+1)]:
        if a[(n-1)-(i+1)] == amx:
            ans*= a[(n-1)-(i+1)]
    amx = a[(n-1)-(i+1)]
    ans %= 1000000007
print ans

Submission status: Runtime Error

Solution code:
    n=int(input())
    l= list(map(int, input().split()))
    r= list(map(int, input().split()))
    l=[0]+l
    r.append(0)
     
    res=1
    for i in range(n):
    	if( (l[i]<l[i+1]) or (r[i]>r[i+1]) ):
    		if( ( (l[i]<l[i+1]) and (r[i]>r[i+1]) ) and (l[i+1]!=r[i]) ):
    			res*=0
    	else:
    		res*=min(l[i],r[i])
    print(res%1000000007)

Submission status: Runtime Error

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

I,J=N-1,0
ans=1
for i in range(N):
    H=min(T[i],A[i])
    if i>0 and T[i-1]<T[i]:
        H=1
        if i+1 <N  and A[i+1]<A[i]:
            if T[i]!=A[i]:
                ans=0
                break
        if i==N-1 and T[i]!=A[i]:
            ans=0
            break
        if T[i] > A[i]
            ans=0
            break
    if i+1 <N and A[i+1] <A[i]:
        H=1
        if i==0 and T[i]!=A[i]:
            ans=0
            break
        if A[i] > T[i]
            ans=0
            break
    if i==0:
        H=1
        if T[i] > A[i]:
            ans =0
            break
    if i==N-1:
        H=1
        if A[i] > T[i]:
            ans = 0
            break
    ans *= H
    ans %= 1000000007
print ans

Submission status: Runtime Error

Solution code:
n=int(input())
l= list(map(int, input().split()))
r= list(map(int, input().split()))
l=[0]+l
r.append(0)

res=1
max=1
if(max(l)!=max(r)):
	res=0
for i in range(n):
	if( (l[i]<l[i+1]) or (r[i]>r[i+1]) ):
		if( ( (l[i]<l[i+1]) and (r[i]>r[i+1]) ) and (l[i+1]!=r[i]) ):
			res*=0
	else:
		res*=min(l[i],r[i])
		res%=1000000007
print(res)

Submission status: Runtime Error

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

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


def f():
    n = int(input())
    t = list(map(int, input().split()))
    a = list(map(int, input().split()))
    r = 0

    if a[-1] > t[-1] or a[0] < t[0]:
        return 0

    for i in range(1,n):
        if m > a[i]:
            m = a[i]
        if (t[i-1] < t[i] and t[i] > m) or t[i] < t[i-1]:
            return 0
    for i in range(n-2,-1,-1):
        if (a[i+1] < a[i] and a[i] > t[i]) or a[i] < a[i+1]:
            return 0

    r = 1
    for i in range(1,n-1):
        if t[i] != t[i-1] or a[i] != a[i+1]:
            continue
        if t[i] < a[i]:
            r = r * t[i] % mod
        else:
            r = r * a[i] % mod

    return r


print(f())