Problem:
 Score : 1100 points    Problem Statement Let us consider a grid of squares with 10^9 rows and N columns. Let (i, j) be the square at the i -th column (1 \leq i \leq N) from the left and j -th row (1 \leq j \leq 10^9) from the bottom.  Snuke has cut out some part of the grid so that, for each i = 1, 2, ..., N , the bottom-most h_i squares are remaining in the i -th column from the left.
Now, he will paint the remaining squares in red and blue.
Find the number of the ways to paint the squares so that the following condition is satisfied:   Every remaining square is painted either red or blue.  For all 1 \leq i \leq N-1 and 1 \leq j \leq min(h_i, h_{i+1})-1 , there are exactly two squares painted red and two squares painted blue among the following four squares: (i, j), (i, j+1), (i+1, j) and (i+1, j+1) .   Since the number of ways can be extremely large, print the count modulo 10^9+7 .      Constraints  1 \leq N \leq 100  1 \leq h_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  h_1  h_2  ...  h_N       Output Print the number of the ways to paint the squares, modulo 10^9+7 .        Sample Input 1 9
2 3 5 4 1 2 4 2 1      Sample Output 1 12800  One of the ways to paint the squares is shown below:   #  # #  #  # # #  #  # # # #  # # #  # # # # # # # # #        Sample Input 2 2
2 2      Sample Output 2 6  There are six ways to paint the squares, as follows:   # #  # #  # #  # #  # #  # #  # #  # #  # #  # #  # #  # #        Sample Input 3 5
2 1 2 1 2      Sample Output 3 256  Every way to paint the squares satisfies the condition.       Sample Input 4 9
27 18 28 18 28 45 90 45 23      Sample Output 4 844733013  Remember to print the number of ways modulo 10^9 + 7 .

Solution (Python):

"""

https://atcoder.jp/contests/agc026/tasks/agc026_d

10101100011
01010011100

→1列目を決めたとする
→2列目の置き方は、左端を決めればすべて決まる
偶数列目を反転してみる？

10 → 11
01    00

10 → 11
10    11

すなわち、偶数列目が反転して表示されるとすると

全て01を入れ替える or 全てそのまま　しか許されない
→すべてそのままが可能なのは全て0 or 1のときのみ

dp[i][0][X] = i列目の下からX個まですべて0の時の通り数
dp[i][1][X] = i列目の下からX個まですべて1の時の通り数
→答えは dp[i][0][0]

if h[i-1] >= h[i]:
    dp[i][0][X] = dp[i-1][1][X] + dp[i-1][0][h[i]]
    dp[i][1][X] = dp[i-1][0][X] + dp[i-1][1][h[i]]
else:
    if X <= h[i-1]:
        dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-h[i-1],mod)
        dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-h[i-1],mod)
    else:
        dp[i][0][X] = (dp[i-1][1][h[i-1]] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-X,mod)
        dp[i][1][X] = (dp[i-1][0][h[i-1]] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-X,mod)

"""

from sys import stdin

N = int(stdin.readline())
h = list(map(int,stdin.readline().split()))
mod = 10**9+7

dp = [ [{},{}] for i in range(N) ]
numlis = set()
numlis.add(1)
for i in h:
    numlis.add(i)
for i in numlis:
    if i <= h[0]:
        dp[0][0][i] = pow(2,h[0]-i,mod)
        dp[0][1][i] = pow(2,h[0]-i,mod)

for i in range(1,N):

    for X in numlis:
        if X > h[i]:
            continue

        if h[i-1] >= h[i]:
            dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i]]) % mod
            dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i]]) % mod
        else:
            if X <= h[i-1]:
                dp[i][0][X] = (dp[i-1][1][X] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-h[i-1],mod) % mod
                dp[i][1][X] = (dp[i-1][0][X] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-h[i-1],mod) % mod
            else:
                dp[i][0][X] = (dp[i-1][1][h[i-1]] + dp[i-1][0][h[i-1]]) * pow(2,h[i]-X,mod) % mod
                dp[i][1][X] = (dp[i-1][0][h[i-1]] + dp[i-1][1][h[i-1]]) * pow(2,h[i]-X,mod) % mod

print ((dp[N-1][0][1] + dp[N-1][1][1]) % mod)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI() + [1]
dp = [1] * (n + 1)

for k in range(n):
    new_dp = [0] * (n + 1)
    for i in range(n + 1):
        if H[i] > H[k]:
            new_dp[i] = dp[k] * 2
        elif H[k - 1] <= H[i]:
            new_dp[i] = dp[i] * 2 * pow(2, H[k] - H[i], mod)
        elif H[k - 1] > H[k]:
            new_dp[i] = dp[i] + dp[k]
        else:
            new_dp[i] = (dp[i] + dp[k - 1]) * pow(2, H[k] - H[k - 1], mod)
        new_dp[i] %= mod
    dp = new_dp


print(dp[-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI() + [1]
dp = [1] * (n + 1)

for k in range(n):
    new_dp = [0] * (n + 1)
    for i in range(n + 1):
        if H[i] > H[k]:
            new_dp[i] = dp[k] * 2
        elif H[k - 1] <= H[i]:
            new_dp[i] = dp[i] * 2 * pow(2, H[k] - H[i], mod)
        elif H[k - 1] > H[k]:
            new_dp[i] = dp[i] - dp[k] + dp[k] * 2
        else:
            new_dp[i] = (dp[i] - dp[k - 1] + dp[k - 1] * 2) * pow(2, H[k] - H[k - 1], mod)
        new_dp[i] %= mod
    dp = new_dp


print(dp[-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI() + [1]
dp = [1] * (n + 1)

for k in range(n):
    new_dp = [0] * (n + 1)
    for i in range(n + 1):
        if H[i] <= H[k]:
            if H[k - 1] <= H[i]:
                new_dp[i] = dp[i] * 2 * pow(2, H[k] - H[i], mod)
            elif H[k - 1] > H[k]:
                new_dp[i] = dp[i] - dp[k] + dp[k] * 2
            else:
                new_dp[i] = (dp[i] - dp[k - 1] + dp[k - 1] * 2) * pow(2, H[k] - H[k - 1], mod)
        else:
            new_dp[i] = dp[k] * 2
        new_dp[i] %= mod
    dp = new_dp


print(dp[-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
H = LI() + [1]
dp = [0] * (n + 1)
ret = pow(2, H[0], mod)
for kk in range(n + 1):
    if H[0] >= H[kk]:
        dp[kk] = pow(2, H[0] - H[kk], mod) * 2
    else:
        dp[kk] = 2


for k in range(1, n):
    new_dp = [0] * (n + 1)
    for i in range(n + 1):
        if H[i] <= H[k]:
            if H[k - 1] <= H[i]:
                new_dp[i] = dp[i] * 2 * pow(2, H[k] - H[i], mod)
            elif H[k - 1] > H[k]:
                new_dp[i] = dp[i] - dp[k] + dp[k] * 2
            else:
                new_dp[i] = (dp[i] - dp[k - 1] + dp[k - 1] * 2) * pow(2, H[k] - H[k - 1], mod)
        else:
            new_dp[i] = dp[k] * 2
        new_dp[i] %= mod
    dp = new_dp


print(dp[-1])

Solution (Python):
mod=10**9+7
n=int(input())
H=list(map(int,input().split()))

def solve(h):
    if not h:
        return 1
    elif len(h)==1:
        return pow(2,h[0],mod)
    N=len(h)
    a=[h[i] for i in range(N)]
    a=list(set(a))
    a.sort()
    comp={i:e+1 for e,i in enumerate(a)}
    data={comp[e]:e for e in comp.keys()}
    data[0]=0
    data[0]=1
    

    dp=[[0 for i in range(len(a)+1)] for j in range(N)]

    i=0
    if h[i+1]>=h[i]:
        id=comp[h[i]]
        id2=comp[h[i+1]]
        for j in range(id,id2+1):
            dp[i][j]=2
        for j in range(0,id):
            dp[i][j]=1
    else:
        id=comp[h[i+1]]
        for j in range(0,id):
            dp[i][j]=pow(2,h[i]-h[i+1],mod)
        dp[i][id]=2*(pow(2,h[i]-h[i+1],mod)-1)
        dp[i][id]%=mod
        id2=comp[h[i]]
        dp[i][id]+=2
        dp[i][id]%=mod

    for i in range(1,N-1):
        if h[i+1]>=h[i]:
            id=comp[h[i]]
            id2=comp[h[i+1]]
            for j in range(id,id2+1):
                dp[i][j]=(2*dp[i-1][id])%mod
            for j in range(0,id):
                dp[i][j]=dp[i-1][j]
        else:
            id=comp[h[i+1]]
            id2=comp[h[i]]
            for j in range(0,id):
                dp[i][j]=(pow(2,h[i]-h[i+1],mod)*dp[i-1][j])%mod
            for j in range(id,id2):
                low=data[j]
                up=data[j+1]-1
                dp[i][id]+=dp[i-1][j]*pow(2,h[i]-up,mod)*(pow(2,up-low+1,mod)-1)
            dp[i][id]%=mod
            dp[i][id]+=2*dp[i-1][id2]
            dp[i][id]%=mod

    ans=0
    id=comp[h[-1]]
    for i in range(0,id):
        low=data[i]
        up=data[i+1]-1
        ans+=dp[N-2][i]*pow(2,h[-1]-up,mod)*(pow(2,up-low+1,mod)-1)
        ans%=mod
    ans+=2*dp[N-2][id]
    ans%=mod
    return ans

ans=pow(2,H.count(1),mod)
check=[i for i in range(n) if H[i]==1]
check=[-1]+check+[n]
for i in range(len(check)-1):
    l,r=check[i],check[i+1]
    ans*=solve(H[l+1:r])
    ans%=mod

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

MOD = 10**9+7
def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N = int(readline())
height = [0]
H = list(map(int, readline().split()))
height.extend(H)

orih, C = compress(height)

L = len(orih)

dp = [0]*L
dp[0] = 1

phidx = 0
for i in range(1, N+1):
    hidx = C[H[i-1]]
    dp2 = [0]*L
    if phidx >= hidx:
        for h in range(hidx+1):
            dp2[h] = (dp[hidx]+dp[h])%MOD
    else:
        if phidx == 0:
            dp2[0] = pow(2, orih[hidx])%MOD
            for h in range(1, hidx+1):
                dp2[h] = pow(2,  orih[hidx]-orih[h]+1, MOD)
        else:
            for h in range(hidx+1):
                dp2[h] = (dp[phidx] + dp[min(phidx, h)])*pow(2, orih[hidx]-orih[max(h, phidx)], MOD)%MOD
    dp = dp2[:]
    phidx = hidx
    
print(dp[0])

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

import numpy as np

MOD = 10**9 + 7

N = int(readline())
H = [int(x) for x in readline().split()]



H_unique = sorted(set([0,1]+H))
H_to_I = {h:i for i,h in enumerate(H_unique)}

items = [0] + [y-x for x,y in zip(H_unique,H_unique[1:])]

inv = pow(2,MOD-2,MOD)
coef = np.array([(pow(2,x+1,MOD)-2) * pow(inv,h,MOD) % MOD for x,h in zip(items,H_unique)],np.int64)

dp = np.zeros(len(H_unique),np.int64)
dp[0] = 1
I1,H1 = 1,1
for H2 in H:
    I2 = H_to_I[H2]
    prev = dp
    dp = np.zeros_like(prev)
    if I1 < I2:
        dp[0] = 2*prev[0]
        dp[1:I1+1] = prev[1:I1+1] * pow(2,H2-H1,MOD)
        dp[I1+1:I2+1] = coef[I1+1:I2+1] * pow(2,H2,MOD) % MOD * prev[0] % MOD
    else:
        prev[0] += prev[I2+1:].sum()
        dp += prev
        dp[0] *= 2
        dp[I2+1:] = 0
    dp %= MOD
    I1,H1 = I2,H2

answer = dp.sum()%MOD
print(answer)

Solution (Python):

import sys

input=sys.stdin.readline

MOD=10**9+7

def powmod(b,e):
    global MOD
    if e==0: return 1
    if e&1: return (powmod((b*b)%MOD,e//2)*b)%MOD
    return powmod((b*b)%MOD,e//2)

n=int(input())
h=[1]+list(map(int,input().split()))

"""

archive=[]


a1=[1]
for i in range(1,n+1):
    if h[i]<=h[i-1]:
        c=0
        while len(a1)>h[i]:
            c+=a1.pop(-1)
        a1[0]=((a1[0]+c)*2)%MOD
    else:
        a1[0]=(a1[0]*2)%MOD
        mul=powmod(2,h[i]-h[i-1])
        for j in range(1,len(a1)):
            a1[j]=(a1[j]*mul)%MOD
        extras=[a1[0]]
        for _ in range(h[i]-h[i-1]-1):
            extras.append(extras[-1]*2)
        a1+=extras[::-1]
    archive.append(a1)

print(sum(a1)%MOD)
"""


root=1      
pos=[]      
sz=1
for i in range(1,n+1):
    if h[i]<=h[i-1]:
        c=0
        while pos and sz-pos[-1][1]>=h[i]:
            a,b=pos.pop(-1)
            c+=(a*(powmod(2,b)-1))%MOD
            sz-=b
        if sz>h[i]:
            a,b=pos.pop(-1)
            pos.append([(a*powmod(2,sz-h[i]))%MOD,b-(sz-h[i])])
            c+=(a*(powmod(2,sz-h[i])-1))%MOD
            sz=h[i]
        root=((root+c)*2)%MOD
    else:
        root=(root*2)%MOD
        mul=powmod(2,h[i]-h[i-1])
        for j in range(len(pos)):
            pos[j][0]=(pos[j][0]*mul)%MOD
        pos.append([root,h[i]-h[i-1]])
        sz=h[i]


for a,b in pos:
    root+=(a*(powmod(2,b)-1))%MOD
print(root%MOD)