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: Time Limit Exceeded

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*=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: Time Limit Exceeded

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*=min(tb,ab)
  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: Time Limit Exceeded

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()]
Chk_T,Chk_A=[False]*n,[False]*n
Max_T,Max_A=[0]*n,[0]*n
Chk_T[0],Chk_A[-1]=True,True
Max_T[0],Max_A[-1]=T[0],A[-1]

for i in range(1,n):
  if T[i]!=T[i-1]:
    Chk_T[i]=True
  Max_T[i]=T[i]
  if A[-i-1]!=A[-i]:
    Chk_A[-i-1]=True
  Max_A[-i-1]=A[-i-1]
ans=1
flag=True
for i in range(n):
  if Chk_T[i]==False and Chk_A[i]==False:
    ans*=min(Max_T[i],Max_A[i])
  elif Chk_T[i]==True and Chk_A[i]==False:
    if Max_T[i]>Max_A[i]:
      flag=False
  elif Chk_T[i]==False and Chk_A[i]==True:
    if Max_T[i]<Max_A[i]:
      flag=False
  else:
    if Max_T[i]!=Max_A[i]:
      flag=False
print(0 if flag==False else ans%mod)

Submission status: Time Limit Exceeded

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()]
Chk_T,Chk_A=[False]*n,[False]*n
Max_T,Max_A=[0]*n,[0]*n
Chk_T[0],Chk_A[-1]=True,True
Max_T[0],Max_A[-1]=T[0],A[-1]

for i in range(1,n):
  if T[i]!=T[i-1]:
    Chk_T[i]=True
  Max_T[i]=T[i]
  if A[-i-1]!=A[-i]:
    Chk_A[-i-1]=True
  Max_A[-i-1]=A[-i-1]
ans=1
flag=True
for i in range(n):
  if Chk_T[i]==False and Chk_A[i]==False:
    ans*=min(Max_T[i],Max_A[i])
  elif Chk_T[i]==True and Chk_A[i]==False:
    if Max_T[i]>Max_A[i]:
      flag=False
  elif Chk_T[i]==False and Chk_A[i]==True:
    if Max_T[i]<Max_A[i]:
      flag=False
  else:
    if Max_T[i]!=Max_A[i]:
      flag=False
print(0 if flag==False else ans%mod)

Submission status: Time Limit Exceeded

Solution code:
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])
        #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])
        #print ("r")
    if (mai2-mai1>1):
      for i in range(mai2-mai1-1):
        s*=mav
    print ( s%(1000000007) )

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
from functools import reduce

MOD = 1000000007

def max_t():
    i, t_max = 0, 0
    for j, v in enumerate(t):
        if v < t_max:
            print(0)
            quit(0)
        if v > t_max:
            t_max = v
            i = j
    return i, t_max


def validate_a(i, t_max):
    for v in a[:i + 1]:
        if v != t_max:
            print(0)
            quit(0)
    for v in a[i + 1:]:
        if v > t_max:
            print(0)
            quit(0)


if __name__ == '__main__':
    n = int(input())
    t = [int(s) for s in input().split()]
    a = [int(s) for s in input().split()]
    i, t_max = max_t()
    validate_a(i, t_max)

    highests = [min(x, y) for x, y in zip(a, t)]
    print(reduce(lambda x, y: x * y % MOD, (v ** ((length - 1) if v < t_max else max(length - 2, 0)) for v, length in ((v, len(list(l))) for v, l in groupby(highests)))))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[0]+list(map(int,input().split()))
b=list(map(int,input().split()))+[0]
c=[[0,0]for i in range(n)]
p=0
mod=10**9+7
for i in range(n,0,-1):
    if a[i-1]!=a[i]:
        c[i-1]=[1,a[i]]
    else:
        c[i-1]=[0,a[i]]
for i in range(n):
    if b[i]!=b[i+1]:
        if c[i][0]==1:
            if b[i]!=c[i][1]:
                print(0)
                break
        else:
            if b[i]<=c[i][1]:
                c[i]=[1,b[i]]
            else:
                print(0)
                break
    else:
        if c[i][0]!=1:
            c[i]=[0,min(b[i],c[i][1])]
        else:
            if c[i][1]>b[i]:
                print(0)
                break
else:
    d=1
    for i in range(n):
        if c[i][0]!=1:
            d*=c[i][1]%mod
    print(d%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t_list = list(map(int, input().split()))
a_list = list(map(int, input().split()))

t_max = -1
t_i = 0
a_max = -1
a_i = 0
ans = 1
mod = 10 ** 9 + 7

for i in range(N):
    t = t_list[i]
    a = a_list[i]
    if t > t_max:
        t_max = t
        t_i = i
    if a >= a_max:
        a_max = a
        a_i = i
if a_max == t_max and t_i <= a_i:
    prev_a = a_list[-1]
    prev_t = t_list[0]
    for i in range(1, t_i):
        t = t_list[i]
        if t == prev_t:
            ans *= prev_t
        prev_t = t
    for i in range(N-2, t_i, -1):
        a = a_list[i]
        if a == prev_a:
            ans *= prev_a
        prev_a = a
    print(ans % mod)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t_list = list(map(int, input().split()))
a_list = list(map(int, input().split()))

t_max = -1
t_i = 0
a_max = -1
a_i = 0
ans = 1
mod = 10 ** 9 + 7

for i in range(N):
    t = t_list[i]
    a = a_list[i]

    if t > t_max:
        t_max = t
        t_i = i
    if a >= a_max:
        a_max = a
        a_i = i
if a_max == t_max and t_i <= a_i:
    prev_a = a_list[-1]
    prev_t = t_list[0]
    for i in range(1, t_i):
        t = t_list[i]
        if t == prev_t:
            ans *= prev_t % mod
        prev_t = t
    for i in range(N-2, t_i, -1):
        a = a_list[i]
        if a == prev_a:
            ans *= prev_a % mod
        prev_a = a
    print(ans % mod)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
h = []
for i in range(N):
    if i == 0:
        h.append(1)
    elif i == N - 1:
        h.append(1)
    else:
        if T[i] > T[i - 1]:
            h.append(1)
            if T[i] > A[i]:
                h[i] = 0
                break
        elif A[i] > A[i + 1]:
            h.append(1)
            if A[i] > T[i]:
                h[i] = 0
                break
        else:
            h.append(min([A[i], T[i]]) % 1000000007)

if max(T) != max(A):
    h.append(0)
    
cnt = 1
for i in range(len(h)):
    cnt *= h[i]
                     
print(cnt % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
r = list(map(int,input().split()))
l1 = max(l)
r1 = max(r)
left = 1
if l[0] == l1:left = 0

right = n-2
if r[-1] == l1:right = n-1

res = 1
if l1 != r1:print(0)
else:
    while l[left] != l1:
        if l[left] == l[left-1]:
            res *= l[left]%1000000007
        left += 1
    while r[right] != r1:
        if r[right] == r[right+1]:
            res *= r[right]%1000000007
        right -=1

    if  left > right:print(0)
    else:
        if  left < right:
            res *= l1**(right-left-1)

        print(res%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
r = list(map(int,input().split()))
l1 = max(l)
r1 = max(r)
left = 1
if l[0] == l1:left = 0

right = n-2
if r[-1] == l1:right = n-1

res = 1
if l1 != r1:print(0)
else:
    while l[left] != l1:
        if l[left] == l[left-1]:
            res *= l[left]
        left += 1
    while r[right] != r1:
        if r[right] == r[right+1]:
            res *= r[right]
        right -=1

    if  left > right:print(0)
    else:
        if  left < right:
            res *= l1**(right-left-1)

        print(res%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
p = 10 ** 9 + 7

B = [10**9] * n

if max(T) != max(A):
    print(0)
    exit()

h = 0

for i, t in enumerate(T):
    if h < t:
        B[i] = 1
        h = t
    else:
        B[i] = h

h = 0

for i, a in zip(range(n-1, -1, -1), A[::-1]):
    if h < a:
        B[i] = 1
        h = a
    elif B[i] == 1 and T[i] > A[i]:
        print(0)
        exit(0)
    elif B[i] > h:
        B[i] = h

ans = 1

for b in B:
    ans *= b

print(ans%p)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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


Th = [[T[0]]]
th_prev = T[0]
for i in range(1, N):
    if T[i] == th_prev:
        Th.append([1, th_prev])
    else:
        Th.append([T[i]])
        th_prev = T[i]

A = A[::-1]
Ah = [[A[0]]]
ah_prev = A[0]
for i in range(1, N):
    if A[i] == ah_prev:
        Ah.append([1, ah_prev])
    else:
        Ah.append([A[i]])
        ah_prev = A[i]
        
Ah = Ah[::-1]
ans = 1
ansable = True
for i in range(N):
    if ansable == False:
        break
    
    elif len(Ah[i]) == 1 and len(Th[i]) == 1:
        if Ah[i][0] != Th[i][0]:
            ans = 0   
            ansable = False
    elif len(Ah[i]) == 1 and len(Th[i]) == 2:
        if Ah[i][0] > Th[i][1]:
            ans = 0
            ansable = False
    elif len(Ah[i]) == 2 and len(Th[i]) == 1:
        if Ah[i][1] < Th[i][0]:
            ans = 0  
            ansable = False
    elif len(Ah[i]) == 2 and len(Th[i]) == 2:
         ans *= (min(Ah[i][1],Th[i][1]))%(10**9+7)
            
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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


Th = [[T[0]]]
th_prev = T[0]
for i in range(1, N):
    if T[i] == th_prev:
        Th.append([1, th_prev])
    else:
        Th.append([T[i]])
        th_prev = T[i]

A = A[::-1]
Ah = [[A[0]]]
ah_prev = A[0]
for i in range(1, N):
    if A[i] == ah_prev:
        Ah.append([1, ah_prev])
    else:
        Ah.append([A[i]])
        ah_prev = A[i]
        
Ah = Ah[::-1]
ans = 1
for i in range(N):
    if len(Ah[i]) == 1 and len(Th[i]) == 1:
        if Ah[i][0] != Th[i][0]:
            ans = 0   
    elif len(Ah[i]) == 1 and len(Th[i]) == 2:
        if Ah[i][0] > Th[i][1]:
            ans = 0
    elif len(Ah[i]) == 2 and len(Th[i]) == 1:
        if Ah[i][1] < Th[i][0]:
            ans = 0       
    elif len(Ah[i]) == 2 and len(Th[i]) == 2:
         ans *= (min(Ah[i][1],Th[i][1]))%(10**9+7)
            
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
count = 0
Tmax = 0
Amax = 0
T2 = []
A2 = []

for i in range(N):
    if T[i] > Tmax:
        T2.append([T[i]])
        Tmax = T[i]
    else:
        T2.append([j for j in range(1,Tmax+1)])
    if A[N-1-i] > Amax:
        A2.append([A[N-1-i]])
        Amax = A[N-1-i]
    else:
        A2.append([j for j in range(1,Amax+1)])

s = 1

for i in range(N):
    count = 0
    for j in T2[i]:
        for z in A2[N-1-i]:
            if j == z:
                count += 1
    if count == 0:
        break
    else:
        s = s * count
        s = s % (10**9+7)

if count == 0:
    print('0')
else:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
def read():
	return [int(i) for i in input().split(" ")]
N = int(input())
T = read()
A = read()
t = [(i != j, i) for i, j in zip(T, [None] + T)]
a = [(i != j, i) for i, j in zip(A, (A + [None])[1:])]
P = 1
for p, q in zip(t, a):
	if(p[0]):
		if(q[0]):
			if(p[1] != q[1]):
				print(0)
				exit()
		elif(q[1] < p[1]):
			print(0)
			exit()
	elif(q[0]):
		if(p[1] < q[1]):
			print(0)
			exit()
	else:
		P *= min(p[1], q[1])
print(P % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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] % mod
        elif T[i] > A[i]:
            if A[i] == A[i + 1]:
                ans *= A[i] % mod
        else:
            if A[i] == A[i + 1]:
                ans *= T[i] % mod
            else:
                print 0
                exit()

print ans % mod

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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]))
s = 1
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]):
            s *= Z[i] % (1000000000 + 7)
    print(sum % (1000000000 + 7))

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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(max(T),max(A)):
        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: Time Limit Exceeded

Solution code:
import sys
n = int(input())
t_list = list(map(lambda number: int(number), input().split(' ')))
a_list = list(map(lambda number: int(number), input().split(' ')))


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

if t_list[-1] != a_list[0]:
    fail()

result = 1
dp = {}
for i in range(1, n - 1):
    key = (t_list[i], t_list[i - 1], a_list[i], a_list[i + 1])
    if key in dp:
        result *= dp[key]
        continue

    if t_list[i] != t_list[i - 1]:
        if a_list[i] != a_list[i + 1]:
            if t_list[i] == a_list[i]:
                dp[(t_list[i], t_list[i - 1], a_list[i], a_list[i + 1])] = 1
                continue
            else:
                fail()
        elif t_list[i] <= a_list[i]:
            dp[(t_list[i], t_list[i - 1], a_list[i], a_list[i + 1])] = 1
            continue
        else:
            fail()
    elif a_list[i] != a_list[i + 1]:
        if a_list[i] <= t_list[i]:
            dp[(t_list[i], t_list[i - 1], a_list[i], a_list[i + 1])] = 1
            continue
        else:
            fail()
    else:
        min_height = min(t_list[i], a_list[i])
        mod = min_height % (10 ** 9 + 7)
        if mod == 0:
            print(0)
            sys.exit()
        else:
            dp[min_height] = mod
            result *= mod
            dp[(t_list[i], t_list[i - 1], a_list[i], a_list[i + 1])] = mod

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

Submission status: Time Limit Exceeded

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

ans = 1
for i in range(N):
    tx = 1
    ax = 1
    tprev = -1 if i == 0 else T[i-1]
    aprev = -1 if i == N-1 else A[i+1]

    if T[i] == tprev:
        tx = T[i]
    else:
        if T[i] > A[i]:
            ans = 0
            break
    if A[i] == aprev:
        ax = A[i]
    else:
        if A[i] > T[i]:
            ans = 0
            break
    ans *= min(tx, ax)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
t_list = list(map(lambda number: int(number), input().split(' ')))
a_list = list(map(lambda number: int(number), input().split(' ')))


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

if t_list[-1] != a_list[0]:
    fail()

candidates = []
result = 1
for i in range(n):
    if i == 0:
        continue
    elif i == n - 1:
        continue
    else:
        if t_list[i] != t_list[i - 1] and a_list[i] != a_list[i + 1]:
            if t_list[i] == a_list[i]:
                continue
            else:
                fail()
        elif t_list[i] != t_list[i - 1]:
            if t_list[i] <= a_list[i]:
                continue
            else:
                fail()
        elif a_list[i] != a_list[i + 1]:
            if a_list[i] <= t_list[i]:
                continue
            else:
                fail()
        else:
            mod = min(t_list[i], a_list[i]) % (10 ** 9 + 7)
            if mod == 0:
                print(0)
                sys.exit()
            else:
                result *= mod

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

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
t_nums = [int(t) for t in raw_input().split()]
a_nums = [int(t) for t in raw_input().split()]

total_so = 1
legal = True
t_max = max(t_nums)
a_max = max(a_nums)
if t_max != a_max:
    print 0
else:
    for i in range(1, N-1):
        if t_nums[i] == t_nums[i-1]:
            if a_nums[i+1] == a_nums[i]:
                total_so *= min(t_nums[i], a_nums[i])
            elif a_nums[i+1] > a_nums[i]:
                legal = False
                break
            else:
                if t_nums[i] < a_nums[i]:
                    legal = False
                    break
                
        elif t_nums[i] < t_nums[i-1]:
            legal = False
            break
        else:
            if a_nums[i] < t_nums[i]:
                legal = False
                break
            
    if legal:        
        print total_so % 1000000007
    else:
        print 0

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
t_list = list(map(lambda number: int(number), input().split(' ')))
a_list = list(map(lambda number: int(number), input().split(' ')))


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

if t_list[-1] != a_list[0]:
    fail()

candidates = []
for i in range(n):
    if i == 0:
        candidates.append([t_list[i]])
    elif i == n - 1:
        candidates.append([a_list[i]])
    else:
        if t_list[i] != t_list[i - 1] and a_list[i] != a_list[i + 1]:
            if t_list[i] == a_list[i]:
                candidates.append([t_list[i]])
            else:
                fail()
        elif t_list[i] != t_list[i - 1]:
            if t_list[i] <= a_list[i]:
                candidates.append([t_list[i]])
            else:
                fail()
        elif a_list[i] != a_list[i + 1]:
            if a_list[i] <= t_list[i]:
                candidates.append([a_list[i]])
            else:
                fail()
        else:
            candidates.append([1, min(t_list[i], a_list[i])])


result = 1

for c in candidates:
    if len(c) == 1:
        continue
    else:
        partial = c[1] % (10**9 + 7)
        if partial == 0:
            print(0)
            sys.exit()
        else:
            result *= partial
print(result % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

def union(x,y):
    if len(x)==1:
        if len(y)==1:
            return (1 if x[0]==y[0] else 0)
        else:
            return (1 if y[-1]>=x[0] else 0)
    if len(x)>1:
        if len(y)==1:
            return (1 if x[-1]>=y[0] else 0)
        else:
            return min(len(x),len(y))

n = int(input())
a = list(map(lambda x: int(x) % MOD, input().split()))
b = list(map(lambda x: int(x) % MOD, input().split()))
x = [[] for _ in range(n)]
y = [[] for _ in range(n)]
z = 1
x[0] += [a[0]]
y[n-1] += [b[n-1]]

for i in range(1,n):
    if a[i-1]<a[i]:
        x[i] += [a[i]]
    else:
        x[i] += list(range(1,a[i]+1))

for j in range(n-1, 0, -1):
    if b[j-1]>b[j]:
        y[j-1] += [b[j-1]]
    else:
        y[j-1] += list(range(1,b[j-1]+1))

for i in range(0,n):
    z *= union(x[i],y[i]) % MOD
    z = z % MOD

print(z)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

def union(x,y):
    if len(x)==1:
        if len(y)==1:
            return (1 if x[0]==y[0] else 0)
        else:
            return (1 if y[-1]>=x[0] else 0)
    if len(x)>1:
        if len(y)==1:
            return (1 if x[-1]>=y[0] else 0)
        else:
            return min(len(x),len(y))

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = [[] for _ in range(n)]
y = [[] for _ in range(n)]
z = 1
x[0] += [a[0]]
y[n-1] += [b[n-1]]

for i in range(1,n):
    if a[i-1]<a[i]:
        x[i] += [a[i]]
    else:
        x[i] += list(range(1,a[i]+1))

for j in range(n-1, 0, -1):
    if b[j-1]>b[j]:
        y[j-1] += [b[j-1]]
    else:
        y[j-1] += list(range(1,b[j-1]+1))

for i in range(0,n):
    z *= union(x[i],y[i]) % MOD
    z = z % MOD

print(z)

Submission status: Time Limit Exceeded

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

tmap = list()
amap = list()
tprev = -1
aprev = -1
for i in range(N):
    if T[i] == tprev:
        tmap.append(tprev)
    else:    
        tmap.append(0)
    if A[N-i-1] == aprev:
        amap.append(aprev)
    else:
        amap.append(0)
    tprev = T[i]
    aprev = A[N-i-1]
ans = 1
for i in range(N):
    tx = tmap[i]
    ax = amap[N-i-1]

    if tx == 0:
        if T[i] > A[i]:
            ans = 0
            break
        tx = 1

    if ax == 0:
        if A[i] > T[i]:
            ans = 0
            break
        ax = 1
    
    ans *= min(tx, ax)
print(ans % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
t_list = list(map(lambda number: int(number), input().split(' ')))
a_list = list(map(lambda number: int(number), input().split(' ')))

if t_list[-1] != a_list[0]:
    print(0)
    sys.exit()

height = 0
candidates = []
for t in t_list:
    if t > height:
        candidates.append([t])
        height = t
    else:
        candidates.append([1, t])

height = 0
for i in list(reversed(range(n))):
    if a_list[i] > height:
        height = a_list[i]
        if len(candidates[i]) == 1 and candidates[i][0] == a_list[i]:
            continue
        elif len(candidates[i]) == 2 and a_list[i] <= candidates[i][1]:
            candidates[i] = [a_list[i]]
        else:
            print(0)
            sys.exit()
    else:
        if len(candidates[i]) == 1 and candidates[i][0] <= a_list[i]:
            continue
        elif len(candidates[i]) == 2:
            candidates[i] = [1, min(candidates[i][1], a_list[i])]
        else:
            print(0)
            sys.exit()

result = 1

for c in candidates:
    if len(c) == 1:
        continue
    else:
        partial = c[1] % (10**9 + 7)
        if partial == 0:
            print(0)
            sys.exit()
        else:
            result *= partial
print(result % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007


def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = [[] for _ in range(n)]
y = [[] for _ in range(n)]
z = 1
x[0] += [a[0]]
y[n-1] += [b[n-1]]



for i in range(1,n):
    if a[i-1]<a[i]:
        x[i] += [a[i]]
    else:
        x[i] += list(range(1,a[i]+1))

for j in range(n-1, 0, -1):
    if b[j-1]>b[j]:
        y[j-1] += [b[j-1]]
    else:
        y[j-1] += list(range(1,b[j-1]+1))

for i in range(0,n):
    z *= len(set(x[i])&set(y[i])) % MOD
    z = z % MOD 

print(z)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
t_list = list(map(lambda number: int(number), input().split(' ')))
a_list = list(map(lambda number: int(number), input().split(' ')))

if t_list[-1] != a_list[0]:
    print(0)
    sys.exit()

height = 0
candidates = []
for t in t_list:
    if t > height:
        candidates.append([t])
        height = t
    else:
        candidates.append([1, t])

height = 0
for i in list(reversed(range(n))):
    if a_list[i] > height:
        height = a_list[i]
        if len(candidates[i]) == 1 and candidates[i][0] == a_list[i]:
            continue
        elif len(candidates[i]) == 2 and a_list[i] <= candidates[i][1]:
            candidates[i] = [a_list[i]]
        else:
            print(0)
            sys.exit()
    else:
        if len(candidates[i]) == 1 and candidates[i][0] <= a_list[i]:
            continue
        elif len(candidates[i]) == 2:
            candidates[i] = [1, min(candidates[i][1], a_list[i])]
        else:
            print(0)
            sys.exit()

result = 1

for c in candidates:
    if len(c) == 1:
        continue
    else:
        result *= c[1]
print(result % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = [[] for _ in range(n)]
y = [[] for _ in range(n)]
z = 1
x[0] += [a[0]]
y[n-1] += [b[n-1]]

for i in range(1,n):
    if a[i-1]<a[i]:
        x[i] += [a[i]]
    else:
        x[i] += list(range(1,a[i]+1))

for j in range(n-1, 0, -1):
    if b[j-1]>b[j]:
        y[j-1] += [b[j-1]]
    else:
        y[j-1] += list(range(1,b[j-1]+1))

for i in range(0,n):
    z *= len(set(x[i])&set(y[i]))
    z = z % MOD

print(z)