Key cutting

n = int(input())
 
segments = [int(x) for x in input().split()]
 
 
 
def inner(start,end):
    if start == end:
 
        total = 1
        if segments[start] == 0:
            total = 0
    else:
        min_value = min(segments[start:end+1])
        idxs = []
        for i in range(start,end+1):
            if segments[i] == min_value:
                idxs.append(i)
            elif segments[i] < min_value:
                idxs = []
                min_value = segments[i]
 
        prev = idxs[0]
        total = 0
        if (min_value > 0):
            total = 1
 
        if prev > start:
            total += inner(start,prev-1)
 
 
        for k in idxs[1:]:
            if prev != k -1:            
                new_start = prev+1
                new_end = k -1
                total += inner(new_start,new_end)
            prev = k
 
        if end > prev:
            total += inner(prev+1,end)
        
    return total
 
 
print(inner(0,n-1))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED