{"problem":{"name":"Distance Sums","description":{"content":"You are given a sequence $D_1, D_2, ..., D_N$ of length $N$. **The values of $D_i$ are all distinct.** Does a tree with $N$ vertices that satisfies the following conditions exist? *   The vertices ar","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc103_d"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence $D_1, D_2, ..., D_N$ of length $N$. **The values of $D_i$ are all distinct.** Does a tree with $N$ vertices that satisfies the following conditions exist?\n\n*   The vertices are numbered $1,2,..., N$.\n*   The edges are numbered $1,2,..., N-1$, and Edge $i$ connects Vertex $u_i$ and $v_i$.\n*   For each vertex $i$, the sum of the distances from $i$ to the other vertices is $D_i$, assuming that the length of each edge is $1$.\n\nIf such a tree exists, construct one such tree.\n\n## Constraints\n\n*   $2 \\leq N \\leq 100000$\n*   $1 \\leq D_i \\leq 10^{12}$\n*   $D_i$ are all distinct.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$D_1$\n$D_2$\n$:$\n$D_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc103_d","tags":[],"sample_group":[["7\n10\n15\n13\n18\n11\n14\n19","1 2\n1 3\n1 5\n3 4\n5 6\n6 7\n\nThe tree shown below satisfies the conditions.\n![image](https://img.atcoder.jp/arc103/92920696862ead4cacf3755c3c8135e0.png)"],["2\n1\n2","\\-1"],["15\n57\n62\n47\n45\n42\n74\n90\n75\n54\n50\n66\n63\n77\n87\n51","1 10\n1 11\n2 8\n2 15\n3 5\n3 9\n4 5\n4 10\n5 15\n6 12\n6 14\n7 13\n9 12\n11 13"]],"created_at":"2026-03-03 11:01:14"}}