B. Queue

Codeforces

IDCF91B

Time2000ms

Memory256MB

Difficulty—

binary searchdata structures

English · Original

Chinese · Translation

Formal · Original

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_. The _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. The airport manager asked you to count for each of _n_ walruses in the queue his displeasure. ## Input The 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). Note 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. ## Output Print _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. [samples]

[{"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 "}]}

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. For each $ i \in \{1, 2, \dots, n\} $, define: - 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 $. - If no such $ j $ exists, the displeasure is $ -1 $. Formally, for each $ i $: Let $$ J_i = \{ j \in \{i+1, i+2, \dots, n\} \mid a_j < a_i \} $$ If $ J_i = \emptyset $, then displeasure of $ i $ is $ -1 $. Otherwise, let $ j^*_i = \max J_i $ (the furthest such $ j $ ahead of $ i $). Then, the displeasure of walrus $ i $ is: $$ j^*_i - i - 1 $$ **Output:** For each $ i = 1 $ to $ n $, output the displeasure of walrus $ i $ as defined above.

Samples

Input #1

6
10 8 5 3 50 45

Output #1

2 1 0 -1 0 -1

Input #2

7
10 4 6 3 2 8 15

Output #2

4 2 1 0 -1 -1 -1

Input #3

5
10 3 1 10 11

Output #3

1 0 -1 -1 -1

API Response (JSON)

{
  "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 beginni...",
      "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_s...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments