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
import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:n+1]))

    if n == 1:
        sys.stdout.write('1\n')
        return

    
    B = a + a

    prev_ge = [-1] * (2 * n)
    stack = []
    for k in range(2 * n):
        bk = B[k]
        while stack and B[stack[-1]] < bk:
            stack.pop()
        if stack:
            prev_ge[k] = stack[-1]
        stack.append(k)

    
    diff = [0] * (n + 1)

    for i in range(n):
        j = prev_ge[n + i]
        if j == i:
            diff[0] += 1
        else:
            p = j % n          # rzeczywista pozycja elementu blokującego
            l = (p + 1) % n    # lewy kpniec zakresu 
            r = i              # prawy koniec zakresu 
            if l <= r:
                diff[l] += 1
                diff[r + 1] -= 1
            else:
                diff[l] += 1
                diff[0] += 1
                diff[r + 1] -= 1

    ans = 0
    cur = 0
    for s in range(n):
        cur += diff[s]
        if cur > ans:
            ans = cur

    sys.stdout.write(str(ans) + '\n')

main()