def gen_lr(X):
    S = []
    res = []
    index = 0
    for i in X:
        while len(S) != 0 and S[-1][0] >= i:
            S.pop()
        if len(S) == 0:
            res.append(-1)
        else:
            res.append(S[-1][1])
        S.append((i,index))
        if index % 10**6 == 0:
            print "b1",index
        index += 1
    return res

def gen_rl(X):
    S = []
    res = []
    index = len(X)-1
    for i in X:
        while len(S) != 0 and S[-1][0] > i:
            S.pop()
        if len(S) == 0:
            res.append((len(X)))
        else:
            res.append(S[-1][1])
        S.append((i,index))
        if index % 10**6 == 0:
            print "b2",index
        index -= 1
    return res

def bs(a,b):
    h = min(a,b)
    r1 = h*(h+1)/2
    d = max(a,b)-min(a,b)
    r2 = (d+1)*(h+1)
    r3 = h*(h+1)/2
    return r1+r2+r3

def actual(A):
    total = 0
    B = gen_lr(A)
    A.reverse()
    C = gen_rl(A)
    C.reverse()
    A.reverse()
    for i in xrange(len(B)):
        b = B[i]
        a = C[i]
        db = abs(b-i+1)
        da = a-i-1
        total += bs(da,db)*A[i]
        if i % 10**6 == 0:
            print "b",i
    print total,"asdf"

def genA():
    i = 290797
    upto = 2*10**9
    A = []
    for x in xrange(upto):
        i = i**2 % 50515093
        A.append(i)
        if x % 10**6 == 0:
            print "a",x
    print "a",x
    return A

actual(genA())