{"problem":{"name":"B. Queue","description":{"content":"There are _n_ walruses standing in a queue in an airport. They are numbered starting from the queue's tail: the 1\\-st walrus stands at the end of the queue and the _n_\\-th walrus stands at the beginni","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF91B"},"statements":[{"statement_type":"Markdown","content":"There are _n_ walruses standing in a queue in an airport. They are numbered starting from the queue's tail: the 1\\-st walrus stands at the end of the queue and the _n_\\-th walrus stands at the beginning of the queue. The _i_\\-th walrus has the age equal to _a__i_.\n\nThe _i_\\-th walrus becomes displeased if there's a younger walrus standing in front of him, that is, if exists such _j_ (_i_ < _j_), that _a__i_ > _a__j_. The displeasure of the _i_\\-th walrus is equal to the number of walruses between him and the furthest walrus ahead of him, which is younger than the _i_\\-th one. That is, the further that young walrus stands from him, the stronger the displeasure is.\n\nThe airport manager asked you to count for each of _n_ walruses in the queue his displeasure.\n\n## Input\n\nThe first line contains an integer _n_ (2 ≤ _n_ ≤ 105) — the number of walruses in the queue. The second line contains integers _a__i_ (1 ≤ _a__i_ ≤ 109).\n\nNote that some walruses can have the same age but for the displeasure to emerge the walrus that is closer to the head of the queue needs to be **strictly younger** than the other one.\n\n## Output\n\nPrint _n_ numbers: if the _i_\\-th walrus is pleased with everything, print \"-1\" (without the quotes). Otherwise, print the _i_\\-th walrus's displeasure: the number of other walruses that stand between him and the furthest from him younger walrus.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"有 #cf_span[n] 只海象站在机场的队列中。它们从队尾开始编号：第 #cf_span[1] 只海象站在队列末尾，第 #cf_span[n] 只海象站在队列开头。第 #cf_span[i] 只海象的年龄为 #cf_span[ai]。\\n\\n如果在第 #cf_span[i] 只海象前面存在一只年龄更小的海象（即存在某个 #cf_span[j]（#cf_span[i < j]）使得 #cf_span[ai > aj]），那么第 #cf_span[i] 只海象就会感到不满。第 #cf_span[i] 只海象的 #cf_span(class=[tex-font-style-underline], body=[displeasure]) 定义为：在他与他前面年龄比他更小的、距离最远的那只海象之间，站立的其他海象的数量。也就是说，那只更年轻的海象离他越远，他的不满程度就越强。\\n\\n机场管理员请你计算队列中每只海象的不满程度。\\n\\n第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 105]）——队列中海象的数量。第二行包含整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 109]）。\\n\\n注意，有些海象可能年龄相同，但只有当队列中靠前的那只海象的年龄 *严格小于* 另一只时，不满才会产生。\\n\\n请输出 #cf_span[n] 个数字：如果第 #cf_span[i] 只海象没有任何不满，请输出 \\\"-1\\\"（不含引号）；否则，输出第 #cf_span[i] 只海象的不满程度：即在他与他前面年龄更小的、距离最远的那只海象之间，其他海象的数量。\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 105]）——队列中海象的数量。第二行包含整数 #cf_span[ai]（#cf_span[1 ≤ ai ≤ 109]）。注意，有些海象可能年龄相同，但只有当队列中靠前的那只海象的年龄 *严格小于* 另一只时，不满才会产生。\"},{\"iden\":\"output\",\"content\":\"请输出 #cf_span[n] 个数字：如果第 #cf_span[i] 只海象没有任何不满，请输出 \\\"-1\\\"（不含引号）；否则，输出第 #cf_span[i] 只海象的不满程度：即在他与他前面年龄更小的、距离最远的那只海象之间，其他海象的数量。\"},{\"iden\":\"examples\",\"content\":\"输入610 8 5 3 50 45输出2 1 0 -1 0 -1 输入710 4 6 3 2 8 15输出4 2 1 0 -1 -1 -1 输入510 3 1 10 11输出1 0 -1 -1 -1 \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ a = [a_1, a_2, \\dots, a_n] $ be a sequence of integers, where $ a_i $ denotes the age of the $ i $-th walrus, with $ i = 1 $ at the tail and $ i = n $ at the head of the queue.\n\nFor each $ i \\in \\{1, 2, \\dots, n\\} $, define:\n\n- The **displeasure** of walrus $ i $ as the number of walruses strictly between $ i $ and the **furthest** index $ j > i $ such that $ a_j < a_i $.\n- If no such $ j $ exists, the displeasure is $ -1 $.\n\nFormally, for each $ i $:\n\nLet  \n$$\nJ_i = \\{ j \\in \\{i+1, i+2, \\dots, n\\} \\mid a_j < a_i \\}\n$$\n\nIf $ J_i = \\emptyset $, then displeasure of $ i $ is $ -1 $.\n\nOtherwise, let $ j^*_i = \\max J_i $ (the furthest such $ j $ ahead of $ i $).\n\nThen, the displeasure of walrus $ i $ is:  \n$$\nj^*_i - i - 1\n$$\n\n**Output:** For each $ i = 1 $ to $ n $, output the displeasure of walrus $ i $ as defined above.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF91B","tags":["binary search","data structures"],"sample_group":[["6\n10 8 5 3 50 45","2 1 0 -1 0 -1"],["7\n10 4 6 3 2 8 15","4 2 1 0 -1 -1 -1"],["5\n10 3 1 10 11","1 0 -1 -1 -1"]],"created_at":"2026-03-03 11:00:39"}}