D. Queue

Codeforces

IDCF92D

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresdp

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[n] 个整数 #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[n] 个整数 #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 set of indices $ J_i = \{ j \mid i < j \leq n \text{ and } a_j < a_i \} $. - If $ J_i = \emptyset $, then the displeasure of walrus $ i $ is $ -1 $. - Otherwise, let $ j^*_i = \max J_i $ (the furthest walrus ahead of $ i $ that is strictly younger). - Then the displeasure of walrus $ i $ is $ j^*_i - i - 1 $. Output the displeasure for each $ i = 1 $ to $ n $.

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": "D. 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": "CF92D"
  },
  "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