{"raw_statement":[{"iden":"statement","content":"Bashar is a very smart person, he invented a new function $F (S)$, where $S$ is a multiset of integers.\n\nThe function $F (S)$ returns the sum of the absolute difference between every pair of elements in $S$.\n\nFor example $F (${$3, 3, 1, 7$}$)$ = $bar.v 3 -3 bar.v$ + $bar.v 3 -1 bar.v$ + $bar.v 3 -7 bar.v$ + $bar.v 3 -1 bar.v$ + $bar.v 3 -7 bar.v$ + $bar.v 1 -7 bar.v$ = $18$.\n\nAfter that Bashar gave Hamada an array $a$ that contains $n$ integers, and asked him to solve this problem.\n\nFor every $k$ such that $(2 <= k <= n)$, Hamada should choose a subsequence of $k$ integers from $a$, such that $F (S)$ is maximised. \n\nHamada couldn't solve the problem and he asked you for help.\n\nThe first line of input contains one integer $n$ $(2 <= n <= 3 times 10^5)$ which is the size of array $a$.\n\nThe second line contains $n$ integers, the $i^(t h)$ one is $a_i$ $(1 <= a_i <= 10^8)$, which is the $i^(t h)$ element in the array.\n\nFor every $k$ such that $(2 <= k <= n)$, print the maximum possible $F (S)$ of a subsequence of size $k$, starting from $k = 2$ ending at $k = n$.\n\na subsequence of size $k$ is a sequnece that can be obtained be removing $n -k$ integers from $a$.\n\n"},{"iden":"input","content":"The first line of input contains one integer $n$ $(2 <= n <= 3 times 10^5)$ which is the size of array $a$.The second line contains $n$ integers, the $i^(t h)$ one is $a_i$ $(1 <= a_i <= 10^8)$, which is the $i^(t h)$ element in the array."},{"iden":"output","content":"For every $k$ such that $(2 <= k <= n)$, print the maximum possible $F (S)$ of a subsequence of size $k$, starting from $k = 2$ ending at $k = n$."},{"iden":"note","content":"a subsequence of size $k$ is a sequnece that can be obtained be removing $n -k$ integers from $a$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s $ be a string representing the hierarchical structure of $ n $ soldiers, where each soldier is encoded as:  \n$$ \\text{Soldier} = \\text{Id} + \\text{Subordinates}, \\quad \\text{Subordinates} = (\\text{Soldier})^* $$  \nEach soldier's ID is a positive integer, and every ID from $ 1 $ to $ n $ appears exactly once.\n\nLet $ \\text{parent}[i] \\in \\{0, 1, 2, \\dots, n\\} $ denote the supervisor of soldier $ i $, where $ \\text{parent}[i] = 0 $ iff soldier $ i $ is the root (king).\n\n**Constraints**  \n1. $ 1 \\le n \\le 1.4 \\times 10^5 $  \n2. $ |s| \\le 10^6 $  \n3. The string $ s $ is well-formed: every opening bracket `(` has a matching closing bracket `)`, and IDs are positive integers in $ [1, n] $, each appearing exactly once.\n\n**Objective**  \nParse the string $ s $ to determine the parent of each soldier $ i \\in \\{1, \\dots, n\\} $, and output $ \\text{parent}[1], \\text{parent}[2], \\dots, \\text{parent}[n] $ as space-separated integers.","simple_statement":"You're given a string representing a tree of soldiers, where each soldier has an ID and may have subordinates in parentheses. The king is the root (no supervisor). Parse the string to find the supervisor of each soldier (1 to n), output supervisor IDs in order, with 0 for the king.","has_page_source":false}