P8148 Sea of Voices | Sea of Voices

“It really feels like a dream.” “What do you mean?” “I saw all your memories from the beginning until now; I saw you coming through moments of joy and moments of loss, again and again. Those scenes appeared before my eyes, like a dream, yet so blurry—I only heard those voices, and only felt that sea of voices surrounding me… Can you hear them?” “Of course. They are my memories, after all.” “Maybe a life is a journey of making sounds. The cry when we are born is a sound that announces our arrival to the world; in challenge after challenge, we sing an unyielding battle song to everything that stands in our way; in the little moments of daily life, we speak to those we cherish about what is deep in our hearts… These sounds, these feelings—could they be the nature of the world we live in?” “Maybe so. Even if we have seen endless scenery along the way, only those sounds that resonate with our hearts—whether from nature or from another soul—can truly change who we are.” “Yes… I hope that in this sea of voices, you will not lose your direction. I look forward to hearing more, about your voice. Hold on to that belief, and keep moving forward.” “You too.” > We'll see creation come undone > > 我们会见证自己存在的印记被世界拂去 > > These bones that bound us will be gone > > 而那些既有的束缚将不再留存 > > We'll stir our spirits till we're one > > 我们会洗涤自己的灵魂直至合为一体 > > Then soft as shadows we'll become > > 然后成为掠影，散失在虚无之中

“But… there were some people whose important voices stayed in my life, yet I can no longer recall them…” “Why is that?” “Let’s make the problem a bit more formal. There are $n$ voices whose sounds I want to recall. Their resonance values—non-negative integers $a_i$—are non-decreasing. At the beginning they do not interfere with each other, but as time goes on, several adjacent voices will intertwine and form a new voice. That is, for any $1\le l\le r\le n$, the $l$-th through the $r$-th voices will intertwine into a new voice, and the resonance value of that new voice is the sum of their resonance values.” “So for example, if $n=3$, $a=[1,2,4]$, then in the end there are $\dfrac{3\times(3+1)}2=6$ voices whose resonance values are $1,2,4,3,6,7$?” “Exactly. Now I will tell you all final resonance values in an unordered way. Can you help me recover the resonance values of the original $n$ voices?” “With pleasure.” ### Brief statement Let $a$ be a non-negative integer sequence of length $n$, satisfying $\forall 1

The first line contains a positive integer $n$, representing the number of original voices. The next line contains $\dfrac{n\times(n+1)}2$ non-negative integers, representing the resonance values of all current voices (in arbitrary order).

Output one line with $n$ non-negative integers, representing the original resonance values $a_i$ of the $n$ voices.

For all data, $1\le n\le 2000$, $0\le a_i\le 10^5$. Subtask 1 (5 pts): $n=2$. Subtask 2 (15 pts): $n=3$. Subtask 3 (30 pts): $n\le 100$. Subtask 4 (50 pts): No special constraints. Translated by ChatGPT 5