The construction of subway in Bertown is almost finished! The President of Berland will visit this city soon to look at the new subway himself.

There are n stations in the subway. It was built according to the Bertown Transport Law:

  1. For each station i there exists exactly one train that goes from this station. Its destination station is pi, possibly pi = i; 
  2. For each station i there exists exactly one station j such that pj = i. 



The President will consider the convenience of subway after visiting it. The convenience is the number of ordered pairs (x, y) such that person can start at station x and, after taking some subway trains (possibly zero), arrive at station y (1 ≤ x, y ≤ n).

The mayor of Bertown thinks that if the subway is not convenient enough, then the President might consider installing a new mayor (and, of course, the current mayor doesn't want it to happen). Before President visits the city mayor has enough time to rebuild some paths of subway, thus changing the values of pi for not more than two subway stations. Of course, breaking the Bertown Transport Law is really bad, so the subway must be built according to the Law even after changes.

The mayor wants to do these changes in such a way that the convenience of the subway is maximized. Help him to calculate the maximum possible convenience he can get! 

Input

The first line contains one integer number n (1 ≤ n ≤ 100000) — the number of stations.

The second line contains n integer numbers p1, p2, ..., pn (1 ≤ pi ≤ n) — the current structure of the subway. All these numbers are distinct.

Output

Print one number — the maximum possible value of convenience.

Examples

Input

3
2 1 3


Output

9


Input

5
1 5 4 3 2


Output

17

Note

In the first example the mayor can change p2 to 3 and p3 to 1, so there will be 9 pairs: (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3).

In the second example the mayor can change p2 to 4 and p3 to 5.
#NYAN NYAN
#░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
#░░░░░░░░░░▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄░░░░░░░░░
#░░░░░░░░▄▀░░░░░░░░░░░░▄░░░░░░░▀▄░░░░░░░
#░░░░░░░░█░░▄░░░░▄░░░░░░░░░░░░░░█░░░░░░░
#░░░░░░░░█░░░░░░░░░░░░▄█▄▄░░▄░░░█░▄▄▄░░░
#░▄▄▄▄▄░░█░░░░░░▀░░░░▀█░░▀▄░░░░░█▀▀░██░░
#░██▄▀██▄█░░░▄░░░░░░░██░░░░▀▀▀▀▀░░░░██░░
#░░▀██▄▀██░░░░░░░░▀░██▀░░░░░░░░░░░░░▀██░
#░░░░▀████░▀░░░░▄░░░██░░░▄█░░░░▄░▄█░░██░
#░░░░░░░▀█░░░░▄░░░░░██░░░░▄░░░▄░░▄░░░██░
#░░░░░░░▄█▄░░░░░░░░░░░▀▄░░▀▀▀▀▀▀▀▀░░▄▀░░
#░░░░░░█▀▀█████████▀▀▀▀████████████▀░░░░
#░░░░░░████▀░░███▀░░░░░░▀███░░▀██▀░░░░░░
#░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
from __future__ import print_function
import os
import sys
import fileinput
import codecs
import operator
import functools
import math
inval = None
file = None
Debug = True
import time

def readSequence(elementType=int, inputLine=None, seperator=' ', strip=True):
    global file
    if (inputLine == None):
        inputLine = file.readline()
    if strip:
        inputLine = inputLine.strip()
    return [elementType(x) for x in inputLine.split(seperator)]

def C(n, r):
    r = min(r, (n - r))
    if (r == 0):
        return 1
    if (r < 0):
        return 0
    numer = functools.reduce(operator.mul, range(n, (n - r), (-1)))
    denom = functools.reduce(operator.mul, range(1, (r + 1)))
    return (numer // denom)

def sumdigit(num):
    num = str(num)
    r = 0
    for x in num:
        r = (r + int(x))
        pass
    return r

def digitListToInt(numList):
    return int(''.join(map(str, numList)))

def listByDigit(digitLen):
    return [0 for _ in range(digitLen)]

def F(n, k):
    ans = 0
    for x in range(1, n):
        ans = (ans + (x * C((n - x), (k - 1))))
        pass
    return ans
    pass

def keyWithMaxValue(d1):
    v = list(d1.values())
    return list(d1.keys())[v.index(max(v))]

def checkProperIrreducible(a, b):
    if (a == 1):
        return True
    if (a == b):
        return False
    if (a > b):
        return checkProperIrreducible(b, a)
    else:
        return checkProperIrreducible(a, (b - a))

class MultiArray(object, ):

    def MultiArray(defaultList, listCount):
        this.Lists[0] = defaultList
        for i in range(1, listCount):
            this.Lists[i] = list()
        pass

    def MultiArray(listCount):
        for i in range(listCount):
            this.Lists[i] = list()
        pass

    def MakeRankList(idx):
        input = this.Lists[0]
        output = ([0] * len(input))
        for (i, x) in enumerate(sorted(range(len(input)), key=(lambda y: input[y]))):
            output[x] = i
        this.Lists[idx] = output
        pass
    pass

def solve():
    solve884c()
    pass

def solve884a():
    rs = RobertsSpaceIndustries = readSequence
    li = rs()
    (n, t) = (li[0], li[1])
    li = rs()
    arr = li
    ans = 0
    avt = 0
    day = 0
    for x in arr:
        avt += (86400 - x)
        day += 1
        if (avt >= t):
            ans = (avt / 86400)
            break
        pass
    write(day)
    pass

def solve884b():
    rs = RobertsSpaceIndustries = readSequence
    (n, x) = rs()
    arr = rs()
    if (((n - 1) + sum(arr)) == x):
        write('YES')
        pass
    else:
        write('NO')
        pass
    pass

def solve884c():
    rs = RobertsSpaceIndustries = readSequence

    def add(x, y):
        return (x + y)
    n = rs()[0]
    arr = rs()
    checkedList = []
    checkList = ([0] * 100001)
    lenarr = len(arr)
    i = 0
    j = 0
    vali = []
    tmp = 0
    while (i < lenarr):
        if (checkList[i] == 0):
            checkList[i] = 1
            tmp += 1
            j = (arr[i] - 1)
            while (j != i):
                checkList[j] = 1
                tmp += 1
                j = (arr[j] - 1)
                pass
            vali.append(tmp)
            tmp = 0
            pass
        else:
            i += 1
        pass
    vali.sort()
    vali.reverse()
    if (len(vali) < 3):
        lent = len(vali)
        if (lent == 1):
            write((vali[0] * vali[0]))
            pass
        else:
            a = (vali[0] + vali[1])
            write((a * a))
            pass
        return
    newli = ([(vali[0] + vali[1])] + vali[2:])

    def mul(x):
        return (x * x)
    ans = sum(map(mul, newli))
    write(ans)
    pass

def solve879a():
    rs = RobertsSpaceIndustries = readSequence
    n = rs()[0]
    cur = 0
    for x in range(n):
        li = rs()
        s = li[0]
        d = li[1]
        i = 0
        while (cur >= (s + (d * i))):
            i += 1
            pass
        cur = (s + (d * i))
    write(cur)
    pass

def solve879b():
    rs = RobertsSpaceIndustries = readSequence
    li = rs()
    (n, k) = (li[0], li[1])
    li = rs()
    arr = li
    wins = ([0] * (n + 3))
    if (k > 600):
        write(n)
        return
    while True:
        a = arr[0]
        b = arr[1]
        if (a > b):
            arr = (([a] + arr[2:]) + [b])
            wins[a] += 1
            if (wins[a] == k):
                write(a)
                return
            pass
        else:
            arr = (([b] + arr[2:]) + [a])
            wins[b] += 1
            if (wins[b] == k):
                write(b)
                return
            pass
        pass
    pass

def solve879c():
    rs = RobertsSpaceIndustries = readSequence
    n = rs()[0]
    onbits = 1023
    offbits = 0
    for x in range(n):
        li = rs(elementType=str)
        if (li[0] == '&'):
            onbits = (onbits & int(li[1]))
            offbits = (offbits & int(li[1]))
            pass
        elif (li[0] == '|'):
            onbits = (onbits | int(li[1]))
            offbits = (offbits | int(li[1]))
            pass
        else:
            onbits = (onbits ^ int(li[1]))
            offbits = (offbits ^ int(li[1]))
            pass
        pass
    orbits = ([0] * 10)
    andbits = ([1] * 10)
    xorbits = ([0] * 10)
    for x in range(10):
        if (((onbits & pow(2, x)) != 0) and ((offbits & pow(2, x)) != 0)):
            orbits[x] = 1
        if (((onbits & pow(2, x)) == 0) and ((offbits & pow(2, x)) == 0)):
            andbits[x] = 0
        if (((onbits & pow(2, x)) == 0) and ((offbits & pow(2, x)) != 0)):
            xorbits[x] = 1
        pass
    orval = 0
    andval = 0
    xorval = 0
    for x in range(len(orbits)):
        orval += (orbits[x] * pow(2, x))
    for x in range(len(andbits)):
        andval += (andbits[x] * pow(2, x))
    for x in range(len(xorbits)):
        xorval += (xorbits[x] * pow(2, x))
    write('3')
    write(('& ' + str(andval)))
    write(('| ' + str(orval)))
    write(('^ ' + str(xorval)))
    pass

def ToSpaceSeperatedString(targetList):
    return ' '.join(map(str, targetList))

def solveTemplate():
    global file
    rl = file.readline
    rs = RobertsSpaceIndustries = readSequence
    li = rs()
    (n, x) = (li[0], li[1])
    pass
inval = None

def write(str1):
    print(str1)
ti = time.time()
file = fileinput.input(inval)
solve()
