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:

  For each station i there exists exactly one train that goes from this station. Its destination station is p_{i}, possibly p_{i} = i;  For each station i there exists exactly one station j such that p_{j} = 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 p_{i} 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 p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ 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 p_2 to 3 and p_3 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 p_2 to 4 and p_3 to 5.

Source: codeforces | Difficulty: MEDIUM
Tags: Graph traversal

Mathematics

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		if rx == ry:
			return False
		if self.rank[rx] < self.rank[ry]:
			(rx, ry) = (ry, rx)
		self.par[rx] += self.par[ry]
		self.par[ry] = rx
		if self.rank[rx] == self.rank[ry]:
			self.rank[rx] += 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]
n = int(input())
p = list(map(int, input().split()))
uf = Unionfind(n)
for i in range(n):
	uf.unite(i, p[i] - 1)
rs = set((uf.root(i) for i in range(n)))
l = []
for r in rs:
	l.append(uf.count(r))
l.sort(reverse=True)
if len(l) == 1:
	print(n * n)
	exit()
ans = (l[0] + l[1]) ** 2
for i in range(2, len(l)):
	ans += l[i] ** 2
print(ans)


n = int(input())
line = list(map(int, input().split()))
(max1, max2) = (-1, -1)
ar = []
colors = [False for i in range(n)]
for i in range(n):
	if colors[i] == True:
		continue
	x = line[i] - 1
	colors[i] = True
	cnt = 1
	while colors[x] == False:
		colors[x] = True
		x = line[x] - 1
		cnt += 1
	if cnt >= max1:
		ar.append(max2)
		max2 = max1
		max1 = cnt
	elif cnt > max2:
		ar.append(max2)
		max2 = cnt
	else:
		ar.append(cnt)
if max2 == -1:
	max2 = 0
ans = (max1 + max2) ** 2
for elem in ar:
	if elem != -1:
		ans += elem ** 2
print(ans)


import sys
sys.setrecursionlimit(10000)

def dfs(root, t):
	time[root] = t
	vis[root] = 1
	stack = [root]
	while len(stack) != 0:
		element = stack.pop()
		time[element] = t
		vis[element] = 1
		for i in graph[element]:
			if vis[i] == 0:
				stack.append(i)
				t += 1
			else:
				c.append(t - time[i] + 1)
n = int(input())
l = list(map(int, input().split()))
graph = [[] for i in range(n)]
for i in range(n):
	graph[i].append(l[i] - 1)
vis = [0] * n
c = []
time = [0] * n
for i in range(n):
	if vis[i] == 0:
		dfs(i, 1)
c.sort()
ans = 0
for i in c:
	ans += i ** 2
if len(c) >= 2:
	print(ans + c[-1] * c[-2] * 2)
else:
	print(ans)


def inp():
	n = int(input())
	return [[int(x), False] for x in input().split()]

def main():
	struct = inp()
	cycles = []
	for s in struct:
		if not s[1]:
			s[1] = True
			cycleLen = 1
			rec = s[0] - 1
			while not struct[rec][1]:
				struct[rec][1] = True
				rec = struct[rec][0] - 1
				cycleLen += 1
			cycles.append(cycleLen)
	(fM, sM, s) = (0, 0, 0)
	for c in cycles:
		if c > fM:
			sM = fM
			fM = c
		elif c > sM:
			sM = c
		s += c ** 2
	s = s - fM ** 2 - sM ** 2 + (fM + sM) ** 2
	return s
answer = main()
print(answer)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]
n = int(input())
p = list(map(int, input().split()))
uf = UnionFind(n)
for i in range(n):
	uf.union(i, p[i] - 1)
a = []
for i in uf.roots():
	a.append([uf.size(i), i])
a = sorted(a, reverse=True)
if len(a) >= 2:
	uf.union(a[0][1], a[1][1])
ans = 0
for i in uf.roots():
	ans += uf.size(i) ** 2
print(ans)


def dfs(u):
	c = 0
	while p[u]:
		c += 1
		(p[u], u) = (0, p[u])
	return c
a = lambda : list(map(int, input().split()))
n = a()
p = [0] + a()
val = sorted([dfs(u) for u in p])
print(sum(list(map(lambda x: x * x, val))) + 2 * val[-1] * val[-2])


n = int(input())
p = list(map(int, input().split()))
ls = []
visited = [False for _ in range(n)]
cnt = 0
for i in range(n):
	j = i
	cnt = 0
	while not visited[j]:
		visited[j] = True
		cnt += 1
		j = p[j] - 1
	if 0 < cnt:
		ls.append(cnt)
ls.sort()
if 1 < len(ls):
	ls[-2] += ls[-1]
	ls.pop()
print(sum(map(lambda x: x ** 2, ls)))


n = int(input())
visited = [0] * n
a = list(map(int, input().split()))
sizes = []
for i in range(n):
	if visited[i]:
		continue
	dest = a[i] - 1
	visited[i] = 1
	count = 1
	while dest != i:
		visited[dest] = 1
		dest = a[dest] - 1
		count += 1
	sizes.append(count)
sizes.sort()
if len(sizes) == 1:
	print(n * n)
	exit()
q = sizes[-1]
r = sizes[-2]
ans = (q + r) * (q + r)
for i in range(len(sizes) - 2):
	ans += sizes[i] * sizes[i]
print(ans)


n = int(input())
p = list(map(int, input().split()))
r = 0
v = [False] * n
c = []
for i in range(n):
	p[i] = p[i] - 1
for i in range(n):
	r = p[i]
	if v[r] == False:
		v[r] = True
		k = 1
		while r != i:
			r = p[r]
			v[r] = True
			k += 1
		c.append(k)
c.sort
c1 = c[len(c) - 1]
if len(c) > 1:
	for i in range(len(c)):
		if c[i] == max(c):
			c1 = c[i]
			break
	c.pop(i)
	for i in range(len(c)):
		if c[i] == max(c):
			c2 = c[i]
			break
	c.pop(i)
	c.append(c1 + c2)
ans = 0
for i in range(len(c)):
	ans += c[i] ** 2
print(ans)


n = int(input())
a = [i for i in map(lambda x: int(x) - 1, input().split())]
(visited, comp) = ([False] * n, 0)
nmbs = []
for (i, v) in enumerate(a):
	if not visited[i]:
		t = i
		while not visited[t]:
			visited[t] = True
			comp += 1
			t = a[t]
		nmbs.append(comp)
		comp = 0
nmbs.sort()
nmbs.reverse()
if len(nmbs) == 1:
	print(nmbs[0] * nmbs[0])
	exit(0)
(nmbs[0], nmbs[1]) = (nmbs[0] + nmbs[1], 0)
print(sum((x * x for x in nmbs)))


n = int(input())
p = [0] + list(map(int, input().split()))

def visit(v):
	res = 0
	while p[v] != 0:
		res += 1
		x = p[v]
		(p[v], v) = (0, x)
	return res
val = sorted([visit(v) for v in range(n + 1)])
print(sum(list([x * x for x in val])) + 2 * val[-1] * val[-2])


n = int(input())
p = list(map(int, input().split()))
for i in range(n):
	p[i] -= 1
res = []
f = [1] * n
for v in p:
	if f[v] == 1:
		f[v] = 0
		sum = 1
		v = p[v]
		while 1:
			if f[v] == 0:
				break
			sum += 1
			f[v] = 0
			v = p[v]
		res.append(sum)
res = sorted(res)
sum = 0
for v in res:
	sum += v * v
sum += res[len(res) - 1] * res[len(res) - 2] * 2
if len(res) == 1:
	print(res[0] * res[0])
else:
	print(sum)


n = int(input())
inp = input()
inp = inp.split()
for i in range(n):
	inp[i] = int(inp[i])
vis = [0 for i in range(n)]
siz = []
for i in range(n):
	if vis[i] == 1:
		continue
	vis[i] = 1
	j = inp[i] - 1
	count = 1
	while vis[j] != 1:
		count += 1
		vis[j] = 1
		j = inp[j] - 1
	siz.append(count)
siz.sort(reverse=True)
if len(siz) == 1:
	print(siz[0] ** 2)
else:
	ans = (siz[0] + siz[1]) ** 2
	for i in range(2, len(siz)):
		ans += siz[i] * siz[i]
	print(ans)


from sys import stdin

def main():
	n = int(stdin.readline())
	ar = list(map(int, stdin.readline().split()))
	check = [False] * n
	ans_list = []
	for i in range(n):
		if not check[i]:
			count = 0
			curr = i
			while not check[curr]:
				check[curr] = True
				count += 1
				curr = ar[curr] - 1
			ans_list.append(count)
	ans_list.sort(reverse=True)
	ans = 0
	if len(ans_list) >= 2:
		ans += (ans_list[0] + ans_list[1]) ** 2
		for i in range(2, len(ans_list)):
			ans += ans_list[i] ** 2
	else:
		ans = ans_list[0] ** 2
	print(ans)
main()


bz = [0 for i in range(1000000)]
to = [0 for i in range(1000000)]
n = 0
n = int(input())
i = 1
for x in input().split():
	to[i] = int(x)
	i += 1
all_num = 0
mx1 = 0
mx2 = 0
for i in range(1, n + 1):
	if bz[i] == 0:
		x = i
		num = 0
		while bz[x] == 0:
			num += 1
			bz[x] = 1
			x = to[x]
		all_num += num ** 2
		if mx1 <= num:
			(mx1, mx2) = (num, mx1)
		elif mx2 < num:
			mx2 = num
print(all_num - mx1 ** 2 - mx2 ** 2 + (mx1 + mx2) ** 2)


n = int(input())
p = list(map(int, input().split()))
p = [i - 1 for i in p]
vis = [False for _ in range(n)]
sz = [0]
for i in range(n):
	j = i
	cnt = 0
	while not vis[j]:
		vis[j] = True
		cnt += 1
		j = p[j]
	if 0 < cnt:
		sz.append(cnt)
sz.sort()
print(sum(list(map(lambda x: x * x, sz))) + 2 * sz[-1] * sz[-2])


import sys
n = int(input())
p = [int(x) - 1 for x in input().split()]
visited = [False] * n
cycles = []
if n == 1:
	print(1)
	sys.exit(0)
for i in range(n):
	if not visited[i]:
		v = p[i]
		visited[v] = True
		k = 1
		while v != i:
			v = p[v]
			visited[v] = True
			k += 1
		cycles.append(k)
cycles.sort()
print(sum(map(lambda x: x ** 2, cycles[:-2])) + sum(cycles[-2:]) ** 2)


n = int(input())
P = [int(p) - 1 for p in input().split()]
seen = [False] * n
res = m0 = m1 = 0
for i in range(n):
	if not seen[i]:
		seen[i] = True
		j = P[i]
		c = 1
		while j != i:
			seen[j] = True
			j = P[j]
			c += 1
		res += c * c
		if c > m0:
			(m0, m1) = (c, m0)
		elif c > m1:
			m1 = c
res += (m0 + m1) * (m0 + m1) - m0 * m0 - m1 * m1
print(res)


n = int(input())
line2 = input().split()
destination = []
visited = []
for i in range(n):
	destination.append(int(line2[i]) - 1)
	visited.append(0)
maxs = [0, 0]
convenience = 0
for i in range(n):
	if visited[i] == 0:
		visited[i] = 1
		cycle_len = 1
		current_node = i
		while destination[current_node] != i:
			current_node = destination[current_node]
			visited[current_node] = 1
			cycle_len += 1
		convenience += cycle_len ** 2
		if cycle_len > min(maxs):
			maxs = [cycle_len, max(maxs)]
convenience += 2 * maxs[0] * maxs[1]
print(convenience)


import sys
n = int(input())
dest = [0] + list(map(int, input().split()))
edge = [1] * (n + 1)
for (i, x) in enumerate(dest):
	if i != x:
		edge[x] = 0
visit_time = [0] * (n + 1)

def solve(i):
	t = visit_time[i] = 1
	while 1:
		t += 1
		i = dest[i]
		if visit_time[i]:
			return (t - 1, t - visit_time[i])
		visit_time[i] = t
component = []
for i in range(1, n + 1):
	if edge[i]:
		component.append(solve(i))
for i in range(1, n + 1):
	if visit_time[i] == 0:
		component.append(solve(i))
component.sort(key=lambda x: (x[0], -x[1]))
if len(component) == 1:
	print(component[0][0] ** 2)
else:
	((x1, _), (x2, _)) = (component.pop(), component.pop())
	component.append((x1 + x2, x1 + x2))
	ans = sum((x * y for (x, y) in component))
	print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = []
for (i, x) in enumerate(a):
	cycle = 0
	while a[i] > 0:
		cycle += 1
		tmp = a[i] - 1
		a[i] -= 1000000000.0
		i = tmp
	ans.append(cycle)
if len(ans) == 1:
	print(ans[0] ** 2)
else:
	ans.sort()
	o = 0
	for x in ans[:-2]:
		o += x ** 2
	print((ans[-1] + ans[-2]) ** 2 + o)


from collections import defaultdict as dd
g = dd(list)

def addE(u, v):
	g[u].append(v)
	g[v].append(u)
n = int(input())
l = [int(x) for x in input().split()]
for i in range(n):
	addE(i + 1, l[i])
visited = [False] * (n + 1)

def dfs(v, count):
	visited[v] = True
	stack = [v]
	while len(stack) != 0:
		cur = stack.pop()
		for ch in g[cur]:
			if visited[ch]:
				continue
			visited[ch] = True
			count += 1
			stack.append(ch)
	return count
ans = []
for i in range(1, n + 1):
	if not visited[i]:
		ans.append(dfs(i, 1))
ans = sorted(ans, reverse=True)
if len(ans) == 1:
	print(ans[0] * ans[0])
else:
	ans[1] += ans[0]
	ans.pop(0)
	print(sum((x * x for x in ans)))


n = int(input())
p = list(map(int, input().split()))
vis = set()
comps = []
for i in range(n):
	if i in vis:
		continue
	sz = 0
	j = i
	while j not in vis:
		vis.add(j)
		sz += 1
		j = p[j] - 1
	comps.append(sz)
comps = sorted(comps)
if len(comps) == 1:
	print(n * n)
else:
	a = comps[-1] + comps[-2]
	ans = a * a + sum([c * c for c in comps[:-2]])
	print(ans)


n = int(input())
p = list(map(int, input().split(' ')))
ls = []
vis = [False for i in range(n)]
cnt = 0
for i in range(n):
	j = i
	cnt = 0
	while not vis[j]:
		vis[j] = True
		cnt += 1
		j = p[j] - 1
	if cnt > 0:
		ls.append(cnt)
ls.sort()
if len(ls) > 1:
	ls[-2] += ls[-1]
	ls.pop()
ans = 0
for i in ls:
	ans = ans + i ** 2
print(ans)


n = int(input())
p = list(map(int, input().split()))
used = [False] * n
nums = list()

def count(i):
	c = 0
	while True:
		if used[i]:
			return c
		else:
			used[i] = True
			i = p[i] - 1
			c += 1
for i in range(n):
	if not used[i]:
		nums.append(count(i))
if n == 1:
	print(1)
elif n == 2:
	print(4)
else:
	nums.sort(reverse=True)
	if len(nums) > 1:
		c = (nums[0] + nums[1]) ** 2
		for i in nums[2:]:
			c += i ** 2
		print(c)
	else:
		print(nums[0] ** 2)


n = int(input())
l = list(map(int, input().split()))
c = [-1] * n
w = -1
mx = -1
tm = -1
ans = 0
for i in range(n):
	sz = 0
	ptr = i
	if c[ptr] == -1:
		w += 1
	while c[ptr] == -1:
		c[ptr] = w
		ptr = l[ptr] - 1
		sz += 1
	if sz > mx:
		(tm, mx) = (mx, sz)
	else:
		tm = max(sz, tm)
	if sz > 0:
		ans += sz ** 2
if tm == -1:
	print(ans)
else:
	print(ans - tm ** 2 - mx ** 2 + (mx + tm) ** 2)


n = int(input())
a = list(map(int, input().split()))
b = [0] * n
k1 = 0
s = []
for i in range(n):
	if b[i] == 0:
		j = a[i] - 1
		k = 1
		b[i] = 1
		sp = [i]
		while b[j] == 0:
			sp.append(j)
			k += 1
			j = a[j] - 1
		s.append(min(k1, k))
		k1 = max(k1, k)
		for u in sp:
			b[u] = k
k2 = max(s)
print(sum(list(map(lambda x: x * x, s))) + k1 * k1 + 2 * k1 * k2)


(COLOR_WHITE, COLOR_GREY, COLOR_BLACK) = (0, 1, 2)

def dfs(targets, colors, node):
	stack = [node]
	size = 0
	while stack:
		node = stack[-1]
		if colors[node] == COLOR_WHITE:
			colors[node] = COLOR_GREY
			size += 1
			neighbor = targets[node]
			if colors[neighbor] == COLOR_WHITE:
				stack.append(neighbor)
			else:
				colors[node] = COLOR_BLACK
				stack.pop()
		else:
			colors[node] = COLOR_BLACK
			stack.pop()
	return size
station_count = int(input())
targets = list(map(lambda node: int(node) - 1, input().split()))
colors = [COLOR_WHITE] * station_count
component_sizes = []
for node in range(station_count):
	if colors[node] == COLOR_WHITE:
		size = dfs(targets, colors, node)
		component_sizes.append(size)
value = sum((size ** 2 for size in component_sizes))
(max1, max2) = (-1, -1)
for size in component_sizes:
	if max1 < size:
		max2 = max1
		max1 = size
	elif max2 < size:
		max2 = size
if max2 > -1:
	value += max1 * max2 * 2
print(value)


n = int(input())
st = list(map(int, input().split()))
if len(st) != n:
	exit()
checked = []
for i in range(n + 5):
	checked.append(False)
cycles = []

def dfs(ver):
	cur = ver
	curcycle = 0
	while not checked[cur]:
		checked[cur] = True
		curcycle += 1
		cur = st[cur] - 1
	cycles.append(curcycle)
for i in range(n):
	dfs(i)
cycles = sorted(cycles, reverse=True)
if len(cycles) == 0:
	print(0)
elif len(cycles) == 1:
	print(cycles[0] ** 2)
else:
	s = (cycles[0] + cycles[1]) ** 2
	for i in range(2, len(cycles)):
		s += cycles[i] ** 2
	print(s)


n = int(input())
P = [int(x) - 1 for x in input().split()]
visited = [-1] * n
cc = []
for i in range(n):
	if visited[i] == -1:
		visited[i] = 0
		amount = 1
		x = P[i]
		while visited[x] == -1:
			visited[x] = 0
			amount += 1
			x = P[x]
		cc += [amount]
cc.sort()
result = 0
merged_size = cc[-1]
if len(cc) > 1:
	merged_size += cc[-2]
result = merged_size * merged_size
for i in range(len(cc) - 2):
	result += cc[i] * cc[i]
print(result)


class node:

	def __init__(self, index):
		self.index = index
		self.nextN = None
		self.visited = 0
n = int(input())
nodes = [node(i + 1) for i in range(n)]
c = [int(i) for i in input().split()]
i = 0
while i < n:
	nodes[i].nextN = nodes[c[i] - 1]
	i += 1
sequence = []
i = 0
news = []
while i < n:
	x = i
	while nodes[x].visited != 1:
		news.append(nodes[x])
		nodes[x].visited = 1
		x = nodes[x].nextN.index - 1
	sequence.append(news)
	news = []
	i += 1
sequence.sort(key=len, reverse=True)
if n == 1:
	print(1)
elif n == 2:
	print(4)
else:
	x = len(sequence[0]) + len(sequence[1])
	x *= x
	som = 0
	for i in range(2, n):
		value = len(sequence[i])
		if value == 0:
			break
		som += value * value
	print(x + som)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
N = int(input())
P = [0] + [int(x) for x in input().split()]
LN = []
C = []
vis = [0] * (N + 1)
for i in range(1, N + 1):
	if vis[i]:
		continue
	vis[i] = 1
	c = [i]
	while True:
		i = P[i]
		if not vis[i]:
			vis[i] = 1
			c.append(i)
		else:
			m = c.index(i)
			C.append((len(c), c, i, m, len(c) - m))
			break
C.sort(reverse=True)
if len(C) == 1:
	print(N * N)
	exit(0)
a = C[0]
b = C[1]
ans = (a[0] + b[0]) ** 2
for c in C[2:]:
	(_, _, _, l, n) = c
	ans += n ** 2 + (2 * n + l + 1) * l // 2
print(ans)


n = int(input())
p = [int(x) for x in input().split()]
p.insert(0, -3)
(max1, max2) = (0, 0)
used = [0] * (n + 1)
count = 0
for i in range(1, n + 1):
	m = 0
	v = i
	while used[p[v]] == 0:
		used[p[v]] = 1
		v = p[v]
		m += 1
	if m > max2:
		max2 = m
	if max2 > max1:
		(max2, max1) = (max1, max2)
	count += m ** 2
count = count - max1 ** 2 - max2 ** 2 + (max1 + max2) ** 2
print(count)


n = int(input())
a = list(map(int, input().split()))
b = []
chains = []
for i in range(n):
	b.append(True)
for i in range(n):
	if b[i]:
		chains.append([i])
		j = i
		b[j] = False
		while a[j] - 1 != chains[-1][0]:
			chains[-1].append(a[j] - 1)
			j = a[j] - 1
			b[j] = False
chainlen = list(map(len, chains))
if len(chains) > 1:
	max1 = max(chainlen)
	max1 = chainlen.index(max1)
	chainlen[max1] *= -1
	max2 = max(chainlen)
	max2 = chainlen.index(max2)
	chainlen[max2] = chainlen[max2] + -1 * chainlen[max1]
	del chainlen[max1]
con = 0
for i in chainlen:
	con += i * i
print(con)


n = int(input())
p = [0] + list(map(int, input().split()))
vis = [0] * (n + 1)
part = []
for i in range(1, n + 1):
	if not vis[i]:
		tot = 0
		x = i
		while not vis[x]:
			tot += 1
			vis[x] = 1
			x = p[x]
		part.append(tot)
part.sort(reverse=True)
if len(part) == 1:
	print(n * n)
else:
	ans = (part[0] + part[1]) ** 2
	for x in part[2:]:
		ans += x * x
	print(ans)


n = int(input())
st = [[int(x), False] for x in input().split()]
groups = []
ptr = 0
while True:
	if ptr >= n:
		break
	if st[ptr][1]:
		ptr += 1
		continue
	cnt = 0
	cur = ptr
	while True:
		st[cur][1] = True
		cnt += 1
		cur = st[cur][0] - 1
		if cur == ptr:
			break
	groups.append(cnt)
	ptr += 1
groups.sort(reverse=True)
if len(groups) == 1:
	print(n ** 2)
else:
	ans = (groups[0] + groups[1]) ** 2
	for (i, cnt) in enumerate(groups):
		if i < 2:
			continue
		ans += cnt ** 2
	print(ans)


import heapq
n = int(input())
grp = list(map(int, input().split()))
heap = []
visited = [False] * n
for i in range(n):
	num = 1
	if visited[i] == False:
		p = grp[i] - 1
		visited[i] = True
		while p != i:
			visited[p] = True
			p = grp[p] - 1
			num += 1
		heapq.heappush(heap, -1 * num)
if len(heap) >= 2:
	val = heapq.heappop(heap) + heapq.heappop(heap)
	val = pow(val, 2)
else:
	val = 0
while heap != []:
	val = val + pow(heapq.heappop(heap), 2)
print(val)


n = int(input())
edges = [int(x) - 1 for x in input().split()]
visited = [False for _ in range(n)]
sizes = []
for i in range(n):
	if visited[i]:
		continue
	visited[i] = True
	component_size = 1
	j = edges[i]
	while not visited[j]:
		visited[j] = True
		component_size += 1
		j = edges[j]
	sizes.append(component_size)
sizes = sorted(sizes)
if len(sizes) > 1:
	sizes[-2] += sizes[-1]
	sizes.pop()
print(sum(map(lambda x: x ** 2, sizes)))


n = int(input())
p = list(map(int, input().split()))
vis = [False] * n
nv = 0
m = 0
cyc = []
while nv < n:
	while vis[m]:
		m += 1
	temp = []
	c = m
	while not vis[c]:
		temp.append(c)
		nv += 1
		vis[c] = True
		c = p[c] - 1
	cyc.append(temp)
size = []
for i in range(len(cyc)):
	size.append(len(cyc[i]))
size = sorted(size)
if len(size) == 1:
	print(size[0] * size[0])
else:
	out = (size[len(size) - 1] + size[len(size) - 2]) * (size[len(size) - 1] + size[len(size) - 2])
	for i in range(len(size) - 2):
		out += size[i] * size[i]
	print(out)


n = int(input())
graph = {}
a = input().split()
for i in range(n):
	graph[i] = int(a[i]) - 1
vis = [False] * n
cycles = []
for i in graph.keys():
	if not vis[i]:
		cv = graph[i]
		vis[i] = True
		size = 1
		while cv != i:
			vis[cv] = True
			cv = graph[cv]
			size += 1
		cycles.append(size)
cycles.sort(reverse=True)
v = 0
if len(cycles) >= 2:
	v += (cycles[0] + cycles[1]) ** 2
	for i in cycles[2:]:
		v += i ** 2
else:
	v = cycles[0] ** 2
print(v)


n = int(input())
tabp = list(map(int, input().split(' ')))
nMax = 0
nSecondMax = 0
counter = 1
Visited = set([])
i = 0
convenience = 0
while i < n:
	Visited.add(i)
	j = tabp[i] - 1
	counter = 1
	while j != i:
		counter += 1
		Visited.add(j)
		j = tabp[j] - 1
	if counter >= nMax:
		nSecondMax = nMax
		nMax = counter
	elif counter >= nSecondMax:
		nSecondMax = counter
	convenience += counter * counter
	for k in range(i + 1, n + 1):
		if k not in Visited:
			i = k
			break
if nSecondMax > 0:
	convenience = convenience - nSecondMax * nSecondMax - nMax * nMax + (nSecondMax + nMax) * (nSecondMax + nMax)
print(convenience)


input()
l = [[int(x) - 1, False] for x in input().split()]
loop = []
for begin in l:
	if begin[1]:
		continue
	count = 0
	nextI = begin[0]
	while not l[nextI][1]:
		l[nextI][1] = True
		nextI = l[nextI][0]
		count += 1
	loop.append(count)
s = sorted(loop, reverse=True)
total = sum(map(lambda x: x * x, s)) + (2 * s[0] * s[1] if len(s) >= 2 else 0)
print(total)


n = int(input())
p = list(map(int, input().split()))
results = list()
stoplist = list()
for i in p:
	if i == 0:
		continue
	j = p[i - 1]
	p[i - 1] = 0
	result = 1
	while j != i:
		t = p[j - 1]
		p[j - 1] = 0
		j = t
		result += 1
	results.append(result)
results.sort(reverse=True)
if len(results) < 2:
	print(sum([x ** 2 for x in results]))
elif len(results) == 2:
	print((results[0] + results[1]) ** 2)
else:
	print(sum([(results[0] + results[1]) ** 2] + [x ** 2 for x in results[2:]]))


n = int(input())
a = list(map(int, input().split()))
vis = [False] * 100005
b = []
m = 0
for i in range(n):
	if not vis[i]:
		m += 1
		cur = i
		len = 0
		while not vis[cur]:
			vis[cur] = True
			len += 1
			cur = a[cur] - 1
		b.append(len)
b.sort()
if m > 1:
	b[-2] += b[-1]
	b.pop()
print(sum(map(lambda x: x ** 2, b)))


n = int(input())
p = list(map(int, input().split()))
for i in range(n):
	p[i] -= 1
color = [0] * n
c = 1
s = []
for i in range(n):
	if color[i] == 0:
		(j, k) = (i, 1)
		color[i] = c
		while p[j] != i:
			j = p[j]
			color[j] = c
			k += 1
		c += 1
		s.append(k)
s.sort()
if len(s) == 1:
	x = s[0] ** 2
else:
	x = (s[-1] + s[-2]) ** 2
	for i in range(len(s) - 2):
		x += s[i] ** 2
print(x)


n = int(input())
a = list(map(int, input().split()))
ans = []
for (i, x) in enumerate(a):
	cycle = 0
	while a[i] > 0:
		cycle += 1
		tmp = a[i] - 1
		a[i] -= n + 1
		i = tmp
	ans.append(cycle)
n = max(ans)
ans.remove(n)
m = max(ans) if ans else 0
if m:
	ans.remove(m)
o = 0
for x in ans:
	o += x ** 2
print((n + m) ** 2 + o)


n = int(input())
p = list(map(int, input().split()))
c = []
visited = [0] * (n + 1)
for i in range(n):
	if visited[p[i]] == 0:
		ct = 1
		t = p[p[i] - 1]
		visited[p[i]] = 1
		while t != p[i]:
			visited[t] = 1
			t = p[t - 1]
			ct += 1
		c.append(ct)
c.sort()
if len(c) == 1:
	print(c[0] ** 2)
else:
	aux = c[-1] + c[-2]
	c = c[:-2] + [aux]
	print(sum((i ** 2 for i in c)))


def dfs(v):
	cnt = 0
	while not vis[v]:
		vis[v] = True
		cnt += 1
		v = town[v]
	return cnt
n = int(input())
town = list(map(int, input().split()))
for i in range(n):
	town[i] -= 1
cur = [0 for _ in range(n)]
vis = [False for _ in range(n)]
answer = [0]
for i in range(n):
	answer.append(dfs(i))
answer.sort()
print(sum(list(map(lambda x: x * x, answer))) + 2 * answer[-1] * answer[-2])


import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
n = int(input())
a = list(mapi())
size = [1] * (n + 1)
par = {i: i for i in range(1, n + 1)}

def find(x):
	if par[x] == x:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def union(x, y):
	x = find(x)
	y = find(y)
	if x == y:
		return
	if size[x] > size[y]:
		(x, y) = (y, x)
	par[x] = y
	size[y] += size[x]
for (i, v) in enumerate(a, 1):
	union(i, v)
b = []
for i in range(1, n + 1):
	if find(i) == i:
		b.append(size[i])
b.sort(reverse=True)
res = 0
for i in range(len(b)):
	if i == 1:
		res -= b[i - 1] ** 2
		res += (b[i] + b[i - 1]) ** 2
	else:
		res += b[i] ** 2
print(res)


n = int(input())
ps = list(map(lambda x: int(x) - 1, input().split()))
sum = 0
maxest_pipe = 0
max_pipe = 0
free_points = set(range(n))
free_points.remove(0)
start_point = 0
current_point = 0
steps = 0
while True:
	steps += 1
	next_point = ps[current_point]
	if next_point in free_points:
		free_points.remove(next_point)
	if next_point == start_point:
		sum += steps * steps
		if steps > maxest_pipe:
			max_pipe = maxest_pipe
			maxest_pipe = steps
		elif steps > max_pipe:
			max_pipe = steps
		steps = 0
		if len(free_points) > 0:
			current_point = free_points.pop()
			start_point = current_point
		else:
			break
	else:
		current_point = next_point
print(sum - max_pipe * max_pipe - maxest_pipe * maxest_pipe + (max_pipe + maxest_pipe) * (max_pipe + maxest_pipe))


from itertools import product

def solve():
	stations = int(input())
	arr = [int(x) - 1 for x in input().split(' ')]
	cycles = []
	discovered = {}
	for i in arr:
		if i in discovered:
			continue
		count = 1
		dest = arr[i]
		path = [dest]
		discovered[dest] = 1
		while dest != i:
			count += 1
			dest = arr[dest]
			path.append(dest)
			discovered[dest] = 1
		cycles.append(path)
	if len(cycles) == 1:
		print(stations * stations)
		return
	longest = sorted(cycles, key=len)[len(cycles) - 2:]
	joined = longest[0] + longest[1]
	cycles = sorted(cycles, key=len)[:len(cycles) - 2]
	cycles.append(joined)
	total = 0
	for cycle in cycles:
		total += len(cycle) ** 2
	print(total)
solve()


n = int(input())
p = [0] * (n + 1)
p[1:n + 1] = list(map(int, input().split()))
c = []
used = [False] * (n + 1)
for i in range(1, n + 1):
	if used[i]:
		continue
	s = list()
	s.append(i)
	used[i] = True
	j = p[i]
	while not used[j]:
		s.append(j)
		used[j] = True
		j = p[j]
	c.append(len(s))
if len(c) == 1:
	print(n * n)
else:
	c.sort()
	c.reverse()
	m = c[0] + c[1]
	print(m * m + sum([d * d for d in c[2:]]))


n = int(input())
data = list(map(int, input().split()))
gp = {i: i for i in range(n)}
sets = {i: [i] for i in range(n)}
for i in range(n):
	(u, v) = (i, data[i] - 1)
	if gp[u] != gp[v]:
		temp = gp[v]
		for i in sets[gp[v]]:
			gp[i] = gp[u]
			sets[gp[u]].append(i)
		del sets[temp]
l = []
for i in sets:
	l.append(len(sets[i]))
l.sort(reverse=True)
n = len(l)
if n == 1:
	print(l[0] * l[0])
else:
	ans = (l[0] + l[1]) ** 2
	for i in range(2, n):
		ans += l[i] ** 2
	print(ans)


n = int(input())
a = [int(x) - 1 for x in input().split()]
vis = [False] * n
cyc = []
ans = 0
for i in range(n):
	if not vis[i]:
		here = a[i]
		vis[i] = True
		ct = 1
		while here != i:
			vis[here] = True
			here = a[here]
			ct += 1
		cyc.append(ct)
cyc.sort()
if len(cyc) > 1:
	cyc.append(cyc.pop() + cyc.pop())
for i in cyc:
	ans += i * i
print(ans if ans > 0 else 1)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	visited = [False] * n
	connected = []
	for i in range(n):
		if not visited[i]:
			visited[i] = True
			cnt = 1
			neighbours = p[i]
			while not visited[neighbours]:
				visited[neighbours] = True
				cnt += 1
				neighbours = p[neighbours]
			connected.append(cnt)
	connected.sort()
	max_size = connected[-1]
	if len(connected) > 1:
		max_size += connected[-2]
	res = max_size ** 2
	for i in range(len(connected) - 2):
		res += connected[i] ** 2
	print(res)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
p = [int(i) - 1 for i in input().split()]
visited = [0 for _ in range(n)]
cycle = [0, 0]
for i in range(n):
	j = i
	count = 0
	while not visited[j]:
		visited[j] = 1
		count += 1
		j = p[j]
	if count > 0:
		cycle.append(count)
cycle.sort()
print(sum([i * i for i in cycle]) + 2 * cycle[-1] * cycle[-2])


n = int(input())
p = [int(x) - 1 for x in input().split()]
encontrados = [False] * n
ciclos = []
for i in range(n):
	if encontrados[i]:
		continue
	ciclos.append([i])
	encontrados[i] = True
	j = p[i]
	while not encontrados[j]:
		ciclos[-1].append(j)
		encontrados[j] = True
		j = p[j]
primero = max([len(x) for x in ciclos])
for i in range(n):
	if len(ciclos[i]) == primero:
		ciclos.pop(i)
		break
if ciclos:
	segundo = max([len(x) for x in ciclos])
else:
	segundo = 0
print((primero + segundo) ** 2 + sum([len(x) ** 2 for x in ciclos]) - segundo ** 2)


from functools import lru_cache
n = int(input())
p = list(map(int, input().split()))
l = []
score = 0
jeden = 0
dwa = 0

@lru_cache(maxsize=10000)
def wzor(s):
	return s * s
for i in range(n):
	if p[i] != 0:
		start = i
		end = p[i]
		lenght = 0
		k = 0
		if start + 1 != p[i]:
			while k - 1 != start:
				k = end
				end = p[end - 1]
				p[k - 1] = 0
				lenght += 1
		else:
			p[end - 1] = 0
			lenght += 1
		if lenght > jeden:
			l.append(dwa)
			dwa = jeden
			jeden = lenght
		elif lenght > dwa:
			l.append(dwa)
			dwa = lenght
		else:
			l.append(lenght)
		length = 0
l.append(jeden + dwa)
for iteam in l:
	if iteam != 1 or iteam != 0:
		score += wzor(iteam)
	elif iteam == 1:
		score += 1
print(int(score))


def dfs(i, Colour, P):
	Stack = [i]
	size = 0
	while Stack:
		v = Stack[-1]
		if Colour[v] == 0:
			Colour[v] = 1
			size += 1
			if Colour[P[v] - 1] == 0:
				Stack.append(P[v] - 1)
			else:
				Colour[v] = 2
				Stack.pop()
		else:
			Colour[v] = 2
			Stack.pop()
	return size
n = int(input())
P = list(map(int, input().split()))
Colour = [0] * n
Len = []
for i in range(n):
	if Colour[i] == 0:
		Len.append(dfs(i, Colour, P))
c1 = 0
c2 = 0
count = 0
for i in Len:
	if c1 <= i:
		c2 = c1
		c1 = i
	elif i > c2:
		c2 = i
for i in Len:
	count += i * i
count += c1 * c2 * 2
print(count)


n = int(input())
(*a,) = map(int, input().split())
vis = set(a)
ans = []
while vis:
	v = vis.pop()
	cur = 1
	while a[v - 1] in vis:
		v = a[v - 1]
		vis.remove(v)
		cur += 1
	ans.append(cur)
s = sum((i ** 2 for i in ans))
if len(ans) == 1:
	print(s)
	exit()
ans.sort()
print(s + 2 * ans[-1] * ans[-2])


n = int(input())
a = list(map(int, input().split()))
if n == 1:
	(print('1'), exit())
if n == 2:
	(print('4'), exit())
b = [i for i in range(0, n + 1)]
r = [1 for i in range(0, n + 1)]

def find(x):
	if b[x] == x:
		return x
	else:
		b[x] = find(b[x])
		return b[x]
for i in range(1, n + 1):
	(x, y) = (find(i), find(a[i - 1]))
	if x == y:
		continue
	if r[x] >= r[y]:
		r[x] += r[y]
		r[y] = 0
		b[y] = x
	else:
		r[y] += r[x]
		r[x] = 0
		b[x] = y
k = 0
for i in range(1, n + 1):
	k += r[i] ** 2
mx1 = max(r[2], r[1])
mx2 = min(r[2], r[1])
for i in range(3, n + 1):
	if r[i] > mx1:
		mx2 = mx1
		mx1 = r[i]
	elif r[i] > mx2:
		mx2 = r[i]
k -= mx1 ** 2 + mx2 ** 2
k += (mx1 + mx2) ** 2
print(k)


n = int(input())
destination = list(map(lambda x: int(x) - 1, input().split()))
visited = [False for __ in range(n)]
maxs = [0, 0]
convenience = 0
for i in range(n):
	if not visited[i]:
		visited[i] = True
		cycle_len = 1
		current_node = i
		while destination[current_node] != i:
			current_node = destination[current_node]
			visited[current_node] = True
			cycle_len += 1
		convenience += cycle_len ** 2
		if cycle_len > min(maxs):
			maxs = [cycle_len, max(maxs)]
convenience += 2 * maxs[0] * maxs[1]
print(convenience)


r = lambda : map(int, input().split())

def main():
	(n,) = r()
	p = [x - 1 for x in r()]
	vis = [False] * n
	lens = []
	for i in range(n):
		if vis[i]:
			continue
		(vis[i], cc) = (True, 1)
		j = p[i]
		while not vis[j]:
			vis[j] = True
			cc += 1
			j = p[j]
		lens.append(cc)
	lens.sort()
	if len(lens) > 1:
		lens[-2] += lens[-1]
		lens.pop()
	print(sum((x * x for x in lens)))
main()