Submission #69535344

---

Source Code Expand

mod = 998244353

def solve1(a):
    # a[i]: -2 or [0, n)
    n = len(a)
    dummy = -2
    accl = [True] * (n + 1)
    for i in range(n):
        accl[i + 1] = accl[i] and (a[i] == dummy or a[i] == i + 1)
    accr = [True] * (n + 1)
    for i in range(n)[::-1]:
        accr[i] = accr[i + 1] and (a[i] == dummy or a[i] == i - 1)

    ans = 0
    # (i-1 <<-> [i]) をつくれる
    avl = [0] * n
    # ([i] <->> i+1) をつくれる
    avr = [0] * n
    for c in range(n):
        if not (accl[c] and accr[c + 1]):
            continue
        if a[c] == dummy:
            ans += n
            avl[c] = 1
            avr[c] = 1
        else:
            ans += 1
            if a[c] == c - 1:
                avl[c] = 1
            if a[c] == c + 1:
                avr[c] = 1
    ans -= sum(avl[c] * avr[c - 1] for c in range(1, n))
    ans %= mod
    return ans

if __name__ == "__main__":
    n = int(input())
    a = tuple(map(lambda s_: int(s_) - 1, input().split()))
    print(solve1(a))

Submission Info

Judge Result