1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
def main():
    n = int(input())

    pearls = list(map(int, input().split()))

    if n == 1:
        print("1")
        return

    pearls2 = pearls + pearls

    closest_bigger = [-1 for _ in range(2*n)]

    covers = [0 for _ in range(n)]

    max_value = (0, 0)

    for i, pearl in enumerate(pearls2):
        if i < n:
            if pearl > max_value[0]:
                max_value = (pearl, 1)
            elif pearl == max_value[0]:
                max_value = (pearl, max_value[1] + 1)
        if i == 0:
            continue
        if pearls2[i-1] >= pearl:
            closest_bigger[i] = i-1
        else:
            prev = closest_bigger[i-1]
            while True:
                if prev == -1:
                    # closest_bigger[i] = -1
                    break
                if prev + n <= i:
                    # closest_bigger[i] = -1
                    break
                if pearls2[prev] >= pearl:
                    closest_bigger[i] = prev
                    break
                prev = closest_bigger[prev]
        if -1 < closest_bigger[i] < n:
            covers[closest_bigger[i]] += 1

    # print(closest_bigger)
    # print(covers)

    delights = 0

    prev_max = -1

    for pearl in pearls:
        if pearl > prev_max:
            delights += 1
            prev_max = pearl

    max_delights = delights
    # print(f"on 0: {delights}")
    for i in range(n):
        delights += covers[i] - 1
        # print(f"on {i}: {delights}")
        if max_value[1] == 1 and pearls[i] == max_value[0]:
            # print("MAX")
            delights += 1

        max_delights = max(
            max_delights,
            delights
        )
    print(max_delights)


if __name__ == "__main__":
    main()