Chain Square

Problem Statement

Chain Square Given a directed tree of N nodes in the form of an array A of size N - 1 , such that there is a directed edge from the node A[i] to the node i + 1 (1 ≤ i You can perform the following operations on it: In one operation, you can break any edge in the tree, dividing that tree into two trees. Break the given tree into a set of trees such that each tree is a directed chain. Your score is the sum of squares of lengths of the directed chains in the set. Print the maximum possible score. Input Format The first line contains a single integer N . The second line contains N - 1 space-separated integers A[i] where A[i] represents the directed edges. Output Format Print a single integer that is the maximum possible score. Constraints 1 ≤ N ≤ 10 5 1 ≤ A[i] ≤ N Examples Input: 5 1 2 3 4 Output: 25 In this example, breaking the edges optimally results in a maximum score of 25.