Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp.keys() and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp.keys():
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
# import random

# N = 10**5
# A = [random.randrange(1,10**9+1) for _ in range(N)]

# import time

def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        ok = True
        if m == 1:
            pre = -1
            for a in A:
                if pre >= a:
                    ok = False
                    break
                pre = a
        else:
            dp = {}
            needreset = 10**15
            exception = set()
            pre = -1
            for a in A:
                ind = a
                for _ in range(40):
                    # 修正
                    if needreset >= ind or ind in exception:
                        if not ind in dp.keys():
                            dp[ind] = 0 if pre < a else 1
                    else:
                        dp[ind] = 0 if pre < a else 1
                        exception.add(ind)
                    # たす
                    if dp[ind] < m:
                        dp[ind] += 1
                        break
                    elif ind == 1:
                        ok = False
                        break
                    else:
                        # 繰り上がり
                        dp[ind] = 1
                        ind -= 1
                if not ok: break
                # 更新
                if pre > a:
                    needreset = a
                    exception = set()
                pre = a

        if ok:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    #dt = time.time()
    main()
    #print(time.time()-dt)

Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
# import random

# N = 10**5
# A = [random.randrange(1,10**9+1) for _ in range(N)]

# import time

def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        ok = True
        if m == 1:
            pre = -1
            for a in A:
                if pre >= a:
                    ok = False
                    break
                pre = a
        else:
            dp = {}
            needreset = 10**15
            exception = set()
            pre = -1
            for a in A:
                ind = a
                for _ in range(40):
                    # 修正
                    if needreset >= ind or ind in exception:
                        if not ind in dp.keys():
                            dp[ind] = 0 if pre < a else 1
                    else:
                        dp[ind] = 0 if pre < a else 1
                        exception.add(ind)
                    # たす
                    if dp[ind] < m:
                        dp[ind] += 1
                        break
                    elif ind == 1:
                        ok = False
                        break
                    else:
                        # 繰り上がり
                        dp[ind] = 1
                        ind -= 1
                if not ok: break
                # 更新
                if pre > a:
                    needreset = a
                    exception = set()
                pre = a

        if ok:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    #dt = time.time()
    main()
    #print(time.time()-dt)

Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
# import random

# N = 10**5
# A = [random.randrange(1,10**9+1) for _ in range(N)]

# import time

def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        ok = True
        if m == 1:
            pre = -1
            for a in A:
                if pre >= a:
                    ok = False
                    break
                pre = a
        else:
            dp = {}
            needreset = 10**15
            exception = set()
            pre = -1
            for a in A:
                ind = a
                for _ in range(100):
                    # 修正
                    if needreset >= ind or ind in exception:
                        if not ind in dp.keys():
                            dp[ind] = 0 if pre < a else 1
                    else:
                        dp[ind] = 0 if pre < a else 1
                        exception.add(ind)
                    # たす
                    if dp[ind] < m:
                        dp[ind] += 1
                        break
                    elif ind == 1:
                        ok = False
                        break
                    else:
                        # 繰り上がり
                        dp[ind] = 1
                        ind -= 1
                if not ok: break
                # 更新
                if pre > a:
                    needreset = a
                    exception = set()
                pre = a

        if ok:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    #dt = time.time()
    main()
    #print(time.time()-dt)

Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
#import random
#
#N = 10**5
#A = [random.randrange(1,10**9+1) for _ in range(N)]


def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        ok = True
        if m == 1:
            pre = -1
            for a in A:
                if pre >= a:
                    ok = False
                    break
                pre = a
        else:
            dp = {}
            needreset = 10**15
            exception = set()
            pre = -1
            for a in A:
                ind = a
                for _ in range(100):
                    # 修正
                    if needreset >= ind or ind in exception:
                        if not ind in dp.keys():
                            dp[ind] = 0 if pre < a else 1
                    else:
                        dp[ind] = 0 if pre < a else 1
                        exception.add(ind)
                    # たす
                    if dp[ind] < m:
                        dp[ind] += 1
                        break
                    elif ind == 1:
                        ok = False
                        break
                    else:
                        # 繰り上がり
                        dp[ind] = 1
                        ind -= 1
                if not ok: break
                # 更新
                if pre > a:
                    needreset = a
                    exception = set()
                pre = a

        if ok:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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


def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        ok = True
        dp = {}
        needreset = 10**15
        # これより長かったらdpにあろうがなかろうが存在しないものになる
        exception = set()
        pre = -1
        for a in A:
            ind = a
            for _ in range(100):
                # 修正
                if needreset >= ind or ind in exception:
                    if not ind in dp.keys():
                        dp[ind] = 0 if pre < a else 1
                else:
                    dp[ind] = 0 if pre < a else 1
                    exception.add(ind)
                # たす
                if dp[ind] < m:
                    dp[ind] += 1
                    break
                elif ind == 1:
                    ok = False
                    break
                else:
                    # 繰り上がり
                    dp[ind] = 1
                    ind -= 1
            if not ok: break
            # 更新
            if pre > a:
                needreset = a
                exception = set()
            pre = a

        if ok:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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


def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        ok = True
        dp = {}
        needreset = 10**15
        # これより長かったらdpにあろうがなかろうが存在しないものになる
        exception = set()
        pre = -1
        for a in A:
            ind = a
            for _ in range(100):
                # 修正
                if needreset >= ind or ind in exception:
                    if not ind in dp.keys():
                        dp[ind] = 0 if pre < a else 1
                else:
                    dp[ind] = 0 if pre < a else 1
                    exception.add(ind)
                # たす
                if dp[ind] < m:
                    dp[ind] += 1
                    break
                elif ind == 1:
                    ok = False
                    break
                else:
                    # 繰り上がり
                    dp[ind] = 1
                    ind -= 1
            if not ok: break
            # 更新
            if pre > a:
                needreset = a
                exception = set()
            pre = a

        if ok:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

l = 0
r = N
while r-l > 1:
    m = (r+l)//2
    ok = True
    dp = {}
    needreset = 10**15
    # これより長かったらdpにあろうがなかろうが存在しないものになる
    exception = set()
    pre = -1
    for a in A:
        ind = a
        while True:
            # 修正
            if needreset >= ind or ind in exception:
                if not ind in dp.keys():
                    dp[ind] = 0 if pre < a else 1
            else:
                dp[ind] = 0 if pre < a else 1
                exception.add(ind)
            # たす
            if dp[ind] != m:
                dp[ind] += 1
                break
            elif ind == 1:
                ok = False
                break
            else:
                # 繰り上がり
                dp[ind] = 1
                ind -= 1
        if not ok: break
        # 更新
        if pre > a:
            needreset = a
            exception = set()
        pre = a

    if ok:
        r = m
    else:
        l = m

print(r)

Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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


Parent = [None for _ in range(2*N+1)]
Points = [(2*N, 0), (0, A[0])]
Parent[0] = (2*N, A[0])
Parent[2*N] = (-1, 1)

for i, a in enumerate(A):
    if i == 0: continue
    lastp, lastd = Points.pop()
    while True:
        if a <= Points[-1][1]:
            lastp, lastd = Points.pop()
        else:
            break
    tmprootdepth = min(lastd, a) - 1
    if tmprootdepth == Points[-1][1]:
        Parent[i] = (Points[-1][0], a-tmprootdepth)
        Points.append((i, a))
    else:
        Parent[lastp] = (i+N, lastd-tmprootdepth)
        Parent[i] = (i+N, a-tmprootdepth)
        Parent[i+N] = (Points[-1][0], tmprootdepth-Points[-1][1])
        Points.append((i+N, tmprootdepth))
        Points.append((i, a))

graph = [[] for _ in range(2*N+1)]
for n in range(2*N):
    if not Parent[n] is None:
        graph[Parent[n][0]].append((Parent[n][1], n))

def dfs(p, span, checked):
    checked[p] = True
    W = 0
    for nd, np in graph[p]:
        if not checked[np]:
            W += dfs(np, span, checked)
    dis_to_parent = Parent[p][1]
    for _ in range(dis_to_parent):
        W = (W-1)//span
        if W <= 0:
            W = 0
            break
    return W

pre = -1
canonly = True
for a in A:
    if a <= pre:
        canonly = False
        break
    pre = a

if canonly:
    print(1)
else:
    l = 1
    r = N+1
    while r-l > 1:
        m = (l+r)//2
        W = dfs(2*N, m, [False]*(2*N+1))
        if W > m:
            l = m
        else:
            r = m

    print(r)

Fixed submission:
import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()