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.

Solution (Python):







MOD = int(1e9) + 7
n = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

Tsa = [0]*n
Asa = [0]*n

if n == 1:
	if T[0] != A[0]:
		print(0)
	else:
		print(1)
elif T[-1] != A[0]:
	print(0)
else:
	
	dai = T[0]
	shou = T[0]
	Tsa[0] = (shou, dai)

	for i in range(1, n):
		if T[i] == dai:
			Tsa[i] = (1, dai)
		else:
			dai = T[i]
			Tsa[i] = (dai, dai)

	
	dai = A[-1]
	shou = A[-1]
	Asa[-1] = (shou, dai)

	for i in reversed(range(-n, -1)):
		if A[i] == dai:
			Asa[i] = (1, dai)
		else:
			dai = A[i]
			Asa[i] = (dai, dai)

	
	ans = 1
	for i in range(n):
		d = max(Tsa[i][0], Asa[i][0])
		u = min(Tsa[i][1], Asa[i][1])

		if d > u:
			ans = 0
			break
		else:
			ans *= u - d + 1
			ans %= MOD
	print(ans)

Solution (Python):

def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    m = 10**9 + 7
    n = read()
    t = reads()
    a = reads()
    if (t != sorted(t)) or (a != sorted(a, reverse=True)) or (max(t) != max(a)):
        print(0)
        return
    if len([1 for ti,ai in zip(t, a) if ti==ai]) == 0:
        print(0)
        return
    
    b = [0] * n
    o = -1
    for i in range(0, n):
        if o != t[i]:
            b[i] = 1
            o = t[i]
            if a[i] < t[i]:
                print(0)
                return
    o = -1
    for i in range(n-1, -1, -1):
        if o != a[i]:
            b[i] = 1
            o = a[i]
            if t[i] < a[i]:
                print(0)
                return
    r = 1
    for i in range(0, n):
        if b[i] == 0:
            r = (r * min(t[i], a[i])) % m
    print(r)

main()

Solution (Python):
n = int(input())
ts = list(map(int, input().split()))
xs = list(map(int, input().split()))

ts = [0] + ts + [ts[-1]]
xs = [xs[0]] + xs + [0]

if n == 1:
    if xs[1] == ts[1]:
        print(1)
    else:
        print(0)
else:
    m = 10**9 + 7
    a = 1
    for i in range(1, n+1):
        if ts[i-1]==ts[i] and xs[i]==xs[i+1]:
            a = a*min(ts[i], xs[i]) % m
        else:
            if ts[i-1]<ts[i] and xs[i]>xs[i+1]:
                if ts[i]!=xs[i]:
                    a = 0
            elif ts[i-1]<ts[i]:
                if xs[i]<ts[i]:
                    a = 0
            else:
                if ts[i]<xs[i]:
                    a = 0
    print(a)

Solution (Python):


def main():
    N = int(input())
    t = list(map(int, input().split()))
    a = list(reversed(list(map(int, input().split()))))

    m = [0] * N

    b = 0
    for i,h in enumerate(t):
        if b != h:
            m[i] = h
            if a[N-i-1] < h:
                print(0)
                return
        b = h
    b = 0
    for j,h in enumerate(a):
        p = N-j-1
        if b != h:
            if m[p] != 0 and m[p] != h:
                print(0)
                return
            else:
                m[p] = h
                if t[p] < h:
                    print(0)
                    return
        b = h
    res = 1
    for k,h in enumerate(m):
        if h == 0:
            res = res * min(a[N-k-1], t[k]) % (pow(10, 9) + 7)
    print(res)
    return

main()

Solution (Python):
N = input()
T = map(int,raw_input().split(" "))
A = map(int,raw_input().split(" "))




note = [1 for i in range(N)]
fx = [0 for i in range(N)]

def solve():
    global note
    if T[-1] != A[0]:
        return 0
    
    prev = 0
    for i in range(N):
        if prev > T[i]:
            return 0
        elif prev == T[i]:
            note[i] = prev
        else:
            note[i] = 1
            prev = T[i]
            fx[i] = T[i]
    prev = 0
    for i in range(N-1,-1,-1):
        if prev > A[i]:
            return 0
        elif prev == A[i]:
            if not fx[i]:
                note[i] = min(note[i],prev)
            else:
                if fx[i] > A[i]:
                    return 0

        else:
            if fx[i] and fx[i] != A[i]:
                return 0
            note[i] = 1
            prev = A[i]

    ans = 1
    for i in range(N):
        if not fx[i]:
            ans = (ans * note[i])%(10**9+7)
    return ans



    





print solve()

Solution (Python):
def work(n, t, a):
    if t[-1] != a[0]:
        return 0

    middle = 0
    for i in xrange(n):
        if t[i] == a[i]:
            if t[i] != t[-1] or t[i] != a[0]:
                return 0
            middle = i
            break
    for i in xrange(middle, n):
        if t[i] < a[i]:
            return 0

    record = [None] * n
    left, right = 0, n - 1

    while left <= right and t[left] < a[left]:
        if not left or t[left] > t[left-1]:
            record[left] = 1
        else:
            record[left] = t[left]
        left += 1
    
    record[left] = 1
    while left < right and a[right] <= t[right]:
        if right == n - 1 or a[right] > a[right+1]:
            record[right] = 1
        else:
            record[right] = a[right]
        right -= 1

    ans = 1
    for i in xrange(n):
        ans = (ans*record[i]) % (10**9+7)
    return ans


n = int(raw_input())
t = map(int, raw_input().split())
a = map(int, raw_input().split())

print work(n, t, a)

Solution (Python):
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
if n==1 and t[0] != a[0]:
    print(0)
    exit()
p = [False for i in range(n)]
p[0] = True
p[n - 1] = True

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

for i in range(n - 2, -1, -1):
    if a[i] > a[i + 1]:
        p[i] = True
        if t[i] < a[i]:
            print(0)
            exit()
h=[min(t[i],a[i]) for i in range(n)]
mod = 10**9 + 7
total = 1
for i in range(n):
    if not p[i]:
        total = (total * h[i]) % mod
print(total)

Solution (Python):



from __future__ import division, print_function, absolute_import, unicode_literals

import sys

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

h = [None] * N

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

odd = False
h[0] = T[0]
for i, (a, b) in enumerate(zip(T[1:], T[:-1]), 1):
    if a != b:
        h[i] = a
    if a < b:
        odd = True
        break

if odd is True:
    print(0)
    sys.exit()

if h[-1] is None:
    h[-1] = A[-1]
elif h[-1] != A[-1]:
    print(0)
    sys.exit()

for i, (a, b) in enumerate(zip(A[::-1][1:], A[::-1][:-1]), 1):
    if a != b:
        if h[N-i-1] is None:
            h[N-i-1] = a
        elif h[N-i-1] != a:
            odd = True
            break
    if a < b:
        odd = True
        break

if odd is True:
    print(0)
    sys.exit()

i = 1
a, b = 0, 0
cnt = 0
ans = 1
flag = False
while i < N-1:
    if h[i] is None:
        flag = True
        a = h[i-1]
        cnt = 0
        while h[i] is None:
            i += 1
            cnt += 1
        b = h[i]
        
        ans = (ans * (min(a, b) ** cnt)) % (10 ** 9 + 7)
        
    else:
        i += 1



odd = False
for i in range(N):
    if h[i] != None:
        cm = h[i]
    if T[i] < cm:
        
        odd = True
        break
cm = None
for i in range(N):
    if h[N-i-1] != None:
        cm = h[N-i-1]
    if A[N-i-1] < cm:
        
        
        odd = True
        break
if odd is True:
    print(0)
    sys.exit()

print(ans)

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

t_left = []
t_right = []
a_left = []
a_right = []
for i in range(N):
    if i == 0:
        t_left.append(T[i])
        t_right.append(T[i])
    else:
        if T[i] > T[i-1]:
            t_left.append(T[i])
            t_right.append(T[i])
        else:
            t_left.append(1)
            t_right.append(T[i])

for i in range(N - 1, -1, -1):
    if i == N - 1:
        a_left.append(A[i])
        a_right.append(A[i])
    else:
        if A[i] > A[i+1]:
            a_left.append(A[i])
            a_right.append(A[i])
        else:
            a_left.append(1)
            a_right.append(A[i])
a_left = a_left[::-1]
a_right = a_right[::-1]




ans = 1
MOD = int(1e9) + 7
for i in range(N):
    l = max(t_left[i], a_left[i])
    r = min(t_right[i], a_right[i])
    if l > r:
        print(0)
        exit()
    else:
        ans *= (r - l + 1)
        ans %= MOD
print(ans % MOD)

Solution (Python):
n = int(raw_input())
t = map(int, raw_input().split())
a = map(int, raw_input().split())
mi = [1 for i in range(n)]
ma = [10**9 for i in range(n)]
for i, e in enumerate(t):
    if i == 0:
        mi[i] = e
        ma[i] = e
    else:
        if e > t[i-1]:
            mi[i] = e
            ma[i] = e
        elif e == t[i-1]:
            ma[i] = e
        else:
            print 0
            exit()

a = a[::-1]
mi = mi[::-1]
ma = ma[::-1]

for i, e in enumerate(a):
    if i == 0:
        if mi[i] <= e <= ma[i]:
            mi[i] = e
            ma[i] = e
        else:
            print 0
            exit()
    else:
        if e > a[i-1]:
            if mi[i] <= e <= ma[i]:
                mi[i] = e
                ma[i] = e
            else:
                print 0
                exit()
        elif e == a[i-1]:
            if mi[i] <= e <= ma[i]:
                ma[i] = e
        else:
            print 0
            exit()
res = 1
for i in range(n):
    res *= ma[i] - mi[i] + 1
    res = res % (10**9+7)
print res % (10**9+7)

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

fixed_peek_t = {}
unfixed_peek_t = {}
fixed_peek_a = {}
unfixed_peek_a = {}

lp = 0
for idx, height in enumerate(T):
    if lp < height:
        fixed_peek_t[idx] = height
    elif idx not in fixed_peek_t:
        unfixed_peek_t[idx] = height
    lp = height

lp = 0
for _idx, height in enumerate(reversed(A)):
    idx = N-1 - _idx
    if lp < height:
        fixed_peek_a[idx] = height
    elif idx not in fixed_peek_a:
        unfixed_peek_a[idx] = height
    lp = height






if max(A) != max(T):
    print(0)
else:
    failflag = 0
    for k,v in fixed_peek_t.items():
        if k not in fixed_peek_a:
            continue
        if v != fixed_peek_a[k]:
            failflag = 1
            break
        if k in unfixed_peek_a and v > unfixed_peek_a[k]:
            failflag = 1
            break
    for k,v in unfixed_peek_t.items():
        if k not in fixed_peek_a:
            continue
        if v < fixed_peek_a[k]:
            failflag = 1
            break
    if failflag == 0:
        cnt = 1
        for k,v in unfixed_peek_t.items():
            if k not in unfixed_peek_a:
                continue
            cnt *= min(v, unfixed_peek_a[k])
            cnt %= 10**9 + 7

        print(cnt)
    else:
        print(0)

Solution (Python):
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')


def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
def join(s):
    return ''.join(s)


def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

nh=zip([1,0,-1,0],[0,1,0,-1])
mod=1000000007


n=i()
t=ii()
a=ii()
just=[0]*n
ub=[INF]*n
lb=[0]*n

def justa(x,y):
    if just[x] in [0,y]:
        just[x]=y
    else:
        print '0'
        sys.exit()

justa(0,t[0])
justa(n-1,a[n-1])

for j in range(1,n):
    if t[j]!=t[j-1]:
        justa(j,t[j])
    else:
        ub[j]=t[j]
for j in reversed(range(0,n-1)):
    if a[j]!=a[j+1]:
        justa(j,a[j])
    else:
        ub[j]=min(ub[j],a[j])

ans=1
for j in range(1,n):
    if just[j]==0:
        ans=ans*ub[j]%mod
    elif just[j]<=ub[j]:
        ans=ans
    else:
        print '0'
        sys.exit()

print ans

Solution (Python):
import math
import sys

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

ans = 1

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

for i in range(N):


    
    if(T[i-1]!=T[i] and T[i]>A[i]):
        print '0'
        sys.exit()
    
    if(T[i-1]>T[i]):
        continue

    if(i==N-1):
        continue

    if(A[i+1]!=A[i] and A[i]>T[i]):
        print '0'
        sys.exit()
    
    if(A[i+1]>A[i]):
        continue

    if(i==0):
        continue

    if((T[i-1]!=T[i])or(A[i+1]!=A[i])):
        continue

    else:
        ans *= min(T[i],A[i])
        ans %= 1000000007

    

print ans

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

M = max(t)
t = [t[0]-1] + t + [t[-1]+1]
a = [a[0]-1] + a + [a[-1]+1]

flag = True
count = 1
for i in range(n):
    if t[i+1] == M and a[i+1] == M:
        flag = False
        if t[i] == M and a[i] == M and t[i+2] == M and a[i+2] == M:
            count = (count * t[i+1]) % (10**9+7)
        continue
    if flag:
        if t[i+1] == t[i]:
            count = (count * t[i+1]) % (10**9+7)
    else:
        if a[i+1] == a[i+2]:
            count = (count * a[i+1]) % (10**9+7)

if flag:
    print(0)
else:
    print(count)

Solution (Python):
from random import random
import math
import re
import fractions

MOD = 10**9+7

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



result = 1

for i in xrange(N):
    et = bt = ea = ba = 0
    if i == 0 or T[i] != T[i-1]:
        et = T[i]
    else:
        bt = T[i]
    if i == N-1 or A[i] != A[i+1]:
        ea = A[i]
    else:
        ba = A[i]
    if ea + et > 0:
        if ea * et > 0 and et != ea:
            result = 0
            break
        if (ea > bt and bt != 0) or (et > ba and ba != 0):
            result = 0
            break
    else:
        result *= min(ba, bt)
        result %= MOD
print(result % MOD)

Solution (Python):
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
R = []
M = 1000000007


def main():
    global R
    global A
    p = -1
    for t in T:
        if t > p: 
            R.append(t)
            p = t
        else:
            R.append(-t)

    
    R = list(reversed(R))
    A = list(reversed(A))

    p = -1
    for i, t in enumerate(A):
        r = R[i]
        if r < 0:
            max_h = -r
            if t > p: 
                p = t
                if t <= max_h:
                    R[i] = t
                else:
                    return 0
            else:
                R[i] = -min(max_h, t)
        else:
            if t > p: 
                p = t
                if t != r:
                    return 0
            else:
                if r > t:
                    return 0

    answer = 1
    for r in R:
        if r > 0:
            answer *= 1
        else:
            max_h = -r
            answer *= max_h
            answer %= M
    return answer
print(main())

Solution (Python):
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

Solution (Python):
from functools import reduce
MOD = 10**9 + 7
class MyRange(object):
    def __init__(self, l, r): 
        self.l = l
        self.r = r

    def __and__(self, other):
        return MyRange(max(self.l, other.l), min(self.r, other.r))

    def __len__(self):
        return self.r - self.l

    def __str__(self):
        return "[{}, {})".format(self.l, self.r)

def hoge(arr):
    res = [MyRange(arr[0], arr[0]+1)]
    for pre, cur in zip(arr, arr[1:]):
        if pre < cur:
            res.append(MyRange(cur, cur+1))
        else:
            res.append(MyRange(1, cur+1))
    return res

if __name__ == "__main__":
    N = int(input())
    T = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    B = [t & a for t, a in zip(hoge(T), hoge(A[::-1])[::-1])]
    
    try:
        C = list(map(len, B))
        print(reduce(lambda a, b: (a * b) % MOD, C))
    except ValueError:
        print(0)

Solution (Python):
N = int(input())

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

kakutei = [-1]* N
for i,a in enumerate(A):
    if i==N-1:
        kakutei[i]= a
        continue
    if a > A[i+1]:
        kakutei[i]=a

for i,t in enumerate(T):
    if i==0:
        kakutei[i]=t
        continue
    if t > T[i-1]:
        if kakutei[i]==-1 or kakutei[i]==t:
            kakutei[i] = t
        else:
            print(0)
            exit(0)

ans = 1
for i in range(N):
    if not(kakutei[i] <= A[i] and kakutei[i] <= T[i]):
        print(0)
        exit(0)
    if kakutei[i]==-1:
        ans*= min(A[i],T[i])
        ans= ans%(10**9 +7)

print(ans)

Solution (Python):
N = int(raw_input())
T_list = map(int, raw_input().split())
A_list = map(int, raw_input().split())

low_list = [1]*N
high_list = [1]*N

t_now = 0
for i in range(N):
    if T_list[i] > t_now:
        t_now = T_list[i]
        low_list[i] = T_list[i]
        high_list[i] = T_list[i]
    else:
        high_list[i] = T_list[i]
a_now = 0
for j in range(N):
    i = N - 1 - j
    if A_list[i] > a_now:
        a_now = A_list[i]
        low_list[i] = max(A_list[i], low_list[i])
        high_list[i] = min(A_list[i], high_list[i])
    else:
        high_list[i] = min(A_list[i], high_list[i])
    
res = 1
for i in range(N):
    if high_list[i] < low_list[i]:
        res = 0
        break
    else:
        res = res*(high_list[i] - low_list[i] + 1) % 1000000007

print res

Solution (Python):
DIV = 10**9 + 7

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


def get_range(a, b):
    if b > a:
        return b, b
    if b == a:
        return (1, b)


left = [(T[0], T[0])]
right = [(A[-1], A[-1])]
for i in range(N - 1):
    a, b = T[i], T[i + 1]
    left.append(get_range(a, b))
    a, b = A[N - i - 1], A[N - i - 2]
    right.append(get_range(a, b))
right = right[::-1]


ans = 1
for i in range(N):
    a1, b1 = left[i]
    a2, b2 = right[i]

    a = max(a1, a2)
    b = min(b1, b2)

    ans *= max((b - a + 1), 0)
    ans %= DIV


print(ans)

Solution (Python):
N = input()
T = map(int, raw_input().split())
A = map(int, raw_input().split())
MOD = 10**9+7

prev = -1
TP = [None for _ in xrange(N)]
for i, t in enumerate(T):
    if t > prev:
        TP[i] = (t, t)
    else:
        TP[i] = (1, t)
    prev = t

prev = -1
AP = [None for _ in xrange(N)]
for i in xrange(N-1, -1, -1):
    a = A[i]
    if a > prev:
        AP[i] = (a, a)
    else:
        AP[i] = (1, a)
    prev = a

ans = 1
for i in xrange(N):
    lt, rt = TP[i]
    la, ra = AP[i]

    if rt < la or ra < lt:
        print 0
        exit()

    s = sorted([lt, rt, la, ra])
    ans = ans * (s[2]-s[1]+1) % MOD
print ans

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, n))
    b = map(int, stdin.readline().split(), repeat(10, n))
    la = [0] * n
    lb = [0] * n
    la[0] = a[0]
    for i in xrange(1, n):
        if a[i-1] < a[i]:
            la[i] = a[i]
        else:
            la[i] = 1
    lb[-1] = b[-1]
    for i in xrange(-2, -n-1, -1):
        if b[i+1] < b[i]:
            lb[i] = b[i]
        else:
            lb[i] = 1
    ans = 1
    for i in xrange(n):
        if a[i] < lb[i] or b[i] < la[i]:
            print 0
            return
        l = la[i] if la[i] > lb[i] else lb[i]
        r = b[i] if b[i] < a[i] else a[i]
        ans = ans * (r - l + 1) % 1000000007
    print ans
main()

Solution (Python):


N = input()
heights = [0] * N
line = raw_input()
T = map(int, line.split())
line = raw_input()
A = map(int, line.split())

def cal():
    preMax = 0
    for i in xrange(N):
        if T[i] > preMax:
            heights[i] = T[i]
            preMax = T[i]
        else:
            heights[i] = -preMax

    preMax = 0
    for i in xrange(N-1, -1, -1):
        if A[i] > preMax:
            
            if heights[i] > 0 and heights[i] != A[i]:
                return 0
            if heights[i] < 0 and A[i] > -heights[i]:
                return 0
            heights[i] = A[i]
            preMax = A[i]
        else:
            
            if heights[i] > 0 and heights[i] > preMax:
                return 0
            if heights[i] < 0:
                heights[i] = max(heights[i], -preMax)

    total = 1
    for i in xrange(N):
        if heights[i] < 0:
            total *= -heights[i]
            total %= (10 ** 9 + 7)

    return total

print cal()

Solution (Python):
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 (t[i-1] < t[i] and t[i] > a[i]) 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())

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

INF = 10**9
record_A = []
record_B = []

record_A.append((A[0], A[0]))

for i in range(1, N):
    if A[i] == A[i-1]:
        record_A.append((1, record_A[-1][1]))
    else:
        record_A.append((A[i], A[i]))

record_B.append((B[-1], B[-1]))

for i in reversed(range(N-1)):
    if B[i] == B[i+1]:
        record_B.append((1, record_B[-1][1]))
    else:
        record_B.append((B[i], B[i]))

ans = 1
mod = 10**9 + 7
for (lb_a, ub_a), (lb_b, ub_b) in zip(record_A, reversed(record_B)):
    lb, ub = max(lb_a, lb_b), min(ub_a, ub_b)
    if ub - lb < 0:
        print(0)
        break
    ans *= ub - lb + 1
    ans %= mod
else:
    print(ans)

Solution (Python):

import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

mod = 10**9 + 7

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

hmin = [1]*N
hmax = [1]*N
hmin[0] = hmax[0] = T[0]
hmin[N - 1] = hmax[N - 1] = A[N - 1]

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

for i in xrange(1, N - 1):
    if T[i] > T[i - 1]:
        hmin[i] = hmax[i] = T[i]
    else:
        hmax[i] = T[i]
for i in xrange(N - 2, 0, -1):
    if A[i] > A[i + 1]:
        if A[i] > hmax[i]:
            print 0
            exit()
        hmax[i] = hmin[i] = A[i]
    else:
        hmax[i] = min(hmax[i], A[i])

ans = 1
for i in xrange(N):
    ans = ans*(hmax[i] - hmin[i] + 1)%mod

print ans

Solution (Python):
N = int(raw_input())
a = map(int, raw_input().split())
b = map(int, raw_input().split())
low = [1] * N
high = [float('inf')] * N
for i in xrange(N):
    high[i] = min(high[i], a[i])
    if i == 0 or a[i] > a[i-1]:
        low[i] = max(low[i], a[i])
for i in xrange(N):
    high[i] = min(high[i], b[i])
    if i == N-1 or b[i] > b[i+1]:
        low[i] = max(low[i], b[i])
M = 10**9+7
ans = 1
for lo, hi in zip(low, high):
    ans = (ans * max(0, hi - lo + 1)) % M
print ans % M

Solution (Python):
n = int(input())
t = [int(x) for x in input().split()]
a = list(reversed([int(x) for x in input().split()]))

t2 = [(p != q, p) for p, q in zip(t, [None] + t)]
a2 = reversed([(p != q, p) for p, q in zip(a, [None] + a)])

ans = 1
for (tf, tv), (af, av) in zip(t2, a2):
    if tf:
        if af:
            if tv != av:
                ans = 0
                break
        else:
            if tv > av:
                ans = 0
                break
    elif af:
        if tv < av:
            ans = 0
            break
    else:
        ans = (ans * min(tv, av)) % 1000000007

print(ans)

Solution (Python):
import sys

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

ma = [T[0]]
mi = [T[0]]

for i in range(1, N):
    if T[i] != T[i - 1]:
        ma.append(T[i])
        mi.append(T[i])
    else:
        ma.append(T[i])
        mi.append(1)

if mi[N - 1] > A[N - 1] or ma[N - 1] < A[N - 1]:
    print 0
    sys.exit()

ma[N - 1] = min(ma[N - 1], A[N - 1])
mi[N - 1] = max(mi[N - 1], A[N - 1])

for i in range(N - 2, -1, -1):
    if A[i] != A[i + 1]:
        if mi[i] > A[i] or ma[i] < A[i]:
            print 0
            sys.exit()
        ma[i] = min(ma[i], A[i])
        mi[i] = max(mi[i], A[i])
    else:
        ma[i] = min(ma[i], A[i])
        mi[i] = max(mi[i], 1)

cnt = 1
for i in range(N):
    cnt *= (ma[i] - mi[i]) + 1
    cnt %= 10 ** 9 + 7
print cnt