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


def solve():
    input = stdin.readline
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))

    # Dla każdej rotacji k, policz liczbę LR-maximów
    # Kluczowa obserwacja: pracujemy na a+a (długość 2n)
    # ale okno ma długość n

    # Wynik dla rotacji k = liczba i w [k, k+n-1] takich że
    # a[i] = max(a[k..i])

    # Sprytnie: policz contributions każdego elementu
    # Element a[i] jest LR-max dla rotacji k iff
    # nie ma żadnego j w [k, i-1] z a[j] >= a[i]
    # czyli k > last_ge[i], gdzie last_ge[i] = ostatni j<i z a[j]>=a[i]

    # Liczba rotacji gdzie a[i] jest LR-max:
    # k ∈ (last_ge[i], i] ∩ [i-n+1, i]
    # = k ∈ [max(last_ge[i]+1, i-n+1), i]

    # Ale my chcemy MAX sumy, nie sumę!
    # Użyjemy różnic — dla każdej rotacji k,
    # suma = suma contributions wszystkich i

    aa = a + a  # podwojona tablica

    # Oblicz previous_greater_or_equal dla każdego i w aa
    # używając stack
    N = 2 * n
    prev_ge = [-1] * N  # indeks ostatniego j < i z aa[j] >= aa[i]

    stack = []  # malejący stos indeksów
    for i in range(N):
        while stack and aa[stack[-1]] < aa[i]:
            stack.pop()
        prev_ge[i] = stack[-1] if stack else -1
        stack.append(i)

    # Dla każdej rotacji k (k=0..n-1), contribution i jest 1 gdy:
    # k ∈ [max(prev_ge[i]+1, i-n+1), i] i i ∈ [k, k+n-1]
    #
    # Czyli element i ∈ [0, 2n-1] daje +1 rotacjom k z przedziału:
    # lo = max(prev_ge[i] + 1, i - n + 1)
    # hi = min(i, n - 1)  # k musi być w [0, n-1]

    # Użyjemy difference array na rotacjach [0..n-1]
    diff = [0] * (n + 1)

    for i in range(N):
        lo = max(prev_ge[i] + 1, i - n + 1)
        hi = min(i, n - 1)
        if lo <= hi:
            diff[lo] += 1
            if hi + 1 <= n:
                diff[hi + 1] -= 1

    # Policz prefix sum i znajdź max
    cur = 0
    ans = 0
    for k in range(n):
        cur += diff[k]
        ans = max(ans, cur)

    print(ans)


solve()