Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    P = []
    for i in range(N):
        P.append(int(input()))

    # asc
    asc_num = 0
    target = 1
    _dict = {}
    for P_i in P:
        del_flag = False
        if P_i not in _dict.values():
            _dict[P_i] = P_i + 1
        for k, v in _dict.items():
            if v == P_i:
                _dict[k] = P_i + 1 
            elif k-1 == P_i:
                asc_num = max(asc_num, v-k)
        if del_flag:
            del _dict[k]
    for k, v in _dict.items():
        asc_num = max(asc_num, v-k)

    print(N-asc_num)



if __name__ == '__main__':
    solve()

Fixed submission:
N = int(input())
P = []
Q = [0 for i in range(N+1)]
for i in range(1, N+1):
    Q[int(input())] = i

straight = 1
max_straight = 1
for i in range(1, N):
    if Q[i] < Q[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1

print(N - max_straight)

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    P = []
    for i in range(N):
        P.append(int(input()))

    # asc
    asc_num = 0
    target = 1
    _dict = {}
    for P_i in P:
        del_flag = False
        if P_i not in _dict.keys() and P_i not in _dict.values():
            _dict[P_i] = P_i + 1
        for k, v in _dict.items():
            if v == P_i:
                _dict[k] = P_i + 1 
            elif k-1 == P_i:
                asc_num = max(asc_num, v-k)
        if del_flag:
            del _dict[k]
    for k, v in _dict.items():
        asc_num = max(asc_num, v-k)

    print(N-asc_num)



if __name__ == '__main__':
    solve()

Fixed submission:
N = int(input())
P = []
Q = [0 for i in range(N+1)]
for i in range(1, N+1):
    Q[int(input())] = i

straight = 1
max_straight = 1
for i in range(1, N):
    if Q[i] < Q[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1

print(N - max_straight)

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    P = []
    for i in range(N):
        P.append(int(input()))

    # asc
    asc_num = 0
    target = 1
    _dict = {}
    for P_i in P:
        del_flag = False
        if P_i not in _dict.keys() and P_i not in _dict.values():
            _dict[P_i] = P_i + 1
        for k, v in _dict.items():
            if v == P_i:
                _dict[k] = P_i + 1 
    for k, v in _dict.items():
        asc_num = max(asc_num, v-k)

    print(N-asc_num)



if __name__ == '__main__':
    solve()

Fixed submission:
N = int(input())
P = []
Q = [0 for i in range(N+1)]
for i in range(1, N+1):
    Q[int(input())] = i

straight = 1
max_straight = 1
for i in range(1, N):
    if Q[i] < Q[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1

print(N - max_straight)

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N = int(input())
    P = []
    for i in range(N):
        P.append(int(input()))

    # asc
    asc_num = 0
    target = 1
    P_tmp = []
    while target <= N:
        tmp_asc_num = 0
        for P_i in P:
            if P_i == target:
                target += 1
                tmp_asc_num += 1
            else:
                P_tmp.append(P_i)
        P = P_tmp[:]
        P_tmp = []
        asc_num = max(asc_num, tmp_asc_num)

    print(N-asc_num)



if __name__ == '__main__':
    solve()

Fixed submission:
N = int(input())
P = []
Q = [0 for i in range(N+1)]
for i in range(1, N+1):
    Q[int(input())] = i

straight = 1
max_straight = 1
for i in range(1, N):
    if Q[i] < Q[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1

print(N - max_straight)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = []
for i in range(N):
    P.append(int(input()))

def solve():
    # asc
    asc_num = 0
    target = 1
    while target <= N:
        tmp_asc_num = 0
        for P_i in P:
            if P_i == target:
                target += 1
                tmp_asc_num += 1
        asc_num = max(asc_num, tmp_asc_num)

    # desc
    desc_num = 0
    target = N
    while target > 0:
        tmp_desc_num = 0
        for P_i in reversed(P):
            if P_i == target:
                target -= 1
                tmp_desc_num += 1
        desc_num = max(desc_num, tmp_desc_num)

    print(min(N-asc_num, N-desc_num))



if __name__ == '__main__':
    solve()

Fixed submission:
N = int(input())
P = []
Q = [0 for i in range(N+1)]
for i in range(1, N+1):
    Q[int(input())] = i

straight = 1
max_straight = 1
for i in range(1, N):
    if Q[i] < Q[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1

print(N - max_straight)