{"problem":{"name":"I. Bashar and Hamada","description":{"content":"Bashar is a very smart person, he invented a new function $F (S)$, where $S$ is a multiset of integers. The function $F (S)$ returns the sum of the absolute difference between every pair of elements ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10226I"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\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\n[samples]\n\n## Note\n\na subsequence of size $k$ is a sequnece that can be obtained be removing $n -k$ integers from $a$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10226I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}