E. Tufurama

Codeforces

IDCF961E

Time2000ms

Memory256MB

Difficulty—

data structures

English · Original

Chinese · Translation

Formal · Original

One day Polycarp decided to rewatch his absolute favourite episode of well-known TV series "Tufurama". He was pretty surprised when he got results only for season 7 episode 3 with his search query of "Watch Tufurama season 3 episode 7 online full hd free". This got Polycarp confused — what if he decides to rewatch the entire series someday and won't be able to find the right episodes to watch? Polycarp now wants to count the number of times he will be forced to search for an episode using some different method. TV series have _n_ seasons (numbered 1 through _n_), the _i_\-th season has _a__i_ episodes (numbered 1 through _a__i_). Polycarp thinks that if for some pair of integers _x_ and _y_ (_x_ < _y_) exist both season _x_ episode _y_ and season _y_ episode _x_ then one of these search queries will include the wrong results. Help Polycarp to calculate the number of such pairs! ## Input The first line contains one integer _n_ (1 ≤ _n_ ≤ 2·105) — the number of seasons. The second line contains _n_ integers separated by space _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — number of episodes in each season. ## Output Print one integer — the number of pairs _x_ and _y_ (_x_ < _y_) such that there exist both season _x_ episode _y_ and season _y_ episode _x_. [samples] ## Note Possible pairs in the second example: 1. _x_ = 1, _y_ = 2 (season 1 episode 2 season 2 episode 1); 2. _x_ = 2, _y_ = 3 (season 2 episode 3 season 3 episode 2); 3. _x_ = 1, _y_ = 3 (season 1 episode 3 season 3 episode 1). In the third example: 1. _x_ = 1, _y_ = 2 (season 1 episode 2 season 2 episode 1); 2. _x_ = 1, _y_ = 3 (season 1 episode 3 season 3 episode 1).

有一天，Polycarp 决定重看他最喜爱的知名电视剧《Tufurama》的某一集。但他用搜索词 "Watch Tufurama season 3 episode 7 online full hd free" 搜索时，只得到了第七季第三集的结果。这让 Polycarp 感到困惑——如果有一天他决定重看整部剧，却无法找到正确的剧集该怎么办？于是 Polycarp 现在想计算他将不得不使用其他方法搜索剧集的次数。这部电视剧共有 #cf_span[n] 季（编号从 #cf_span[1] 到 #cf_span[n]），第 #cf_span[i] 季有 #cf_span[ai] 集（编号从 #cf_span[1] 到 #cf_span[ai]）。Polycarp 认为，如果存在一对整数 #cf_span[x] 和 #cf_span[y]（#cf_span[x < y]），使得同时存在第 #cf_span[x] 季第 #cf_span[y] 集和第 #cf_span[y] 季第 #cf_span[x] 集，那么其中一个搜索查询就会包含错误的结果。请帮助 Polycarp 计算这样的配对数量！第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 2·105)] —— 季数。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an] #cf_span[(1 ≤ ai ≤ 109)] —— 每季的集数。输出一个整数 —— 满足存在第 #cf_span[x] 季第 #cf_span[y] 集和第 #cf_span[y] 季第 #cf_span[x] 集的配对 #cf_span[x] 和 #cf_span[y]（#cf_span[x < y]）的数量。 ## Input 第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 2·105)] —— 季数。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an] #cf_span[(1 ≤ ai ≤ 109)] —— 每季的集数。 ## Output 输出一个整数 —— 满足存在第 #cf_span[x] 季第 #cf_span[y] 集和第 #cf_span[y] 季第 #cf_span[x] 集的配对 #cf_span[x] 和 #cf_span[y]（#cf_span[x < y]）的数量。 [samples] ## Note 第二个例子中的可能配对：#cf_span[x = 1], #cf_span[y = 2]（第 1 季第 2 集，第 2 季第 1 集）；#cf_span[x = 2], #cf_span[y = 3]（第 2 季第 3 集，第 3 季第 2 集）；#cf_span[x = 1], #cf_span[y = 3]（第 1 季第 3 集，第 3 季第 1 集）。第三个例子中：#cf_span[x = 1], #cf_span[y = 2]（第 1 季第 2 集，第 2 季第 1 集）；#cf_span[x = 1], #cf_span[y = 3]（第 1 季第 3 集，第 3 季第 1 集）。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of seasons. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ denotes the number of episodes in season $ i $. **Constraints** 1. $ 1 \leq n \leq 2 \cdot 10^5 $ 2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Count the number of pairs $ (x, y) \in \mathbb{Z}^2 $ such that: - $ 1 \leq x < y \leq n $, - $ a_x \geq y $, and - $ a_y \geq x $.

Samples

Input #1

5
1 2 3 4 5

Output #1

Input #2

3
8 12 7

Output #2

Input #3

3
3 2 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Tufurama",
    "description": {
      "content": "One day Polycarp decided to rewatch his absolute favourite episode of well-known TV series \"Tufurama\". He was pretty surprised when he got results only for season 7 episode 3 with his search query of ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF961E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One day Polycarp decided to rewatch his absolute favourite episode of well-known TV series \"Tufurama\". He was pretty surprised when he got results only for season 7 episode 3 with his search query of ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有一天，Polycarp 决定重看他最喜爱的知名电视剧《Tufurama》的某一集。但他用搜索词 \"Watch Tufurama season 3 episode 7 online full hd free\" 搜索时，只得到了第七季第三集的结果。这让 Polycarp 感到困惑——如果有一天他决定重看整部剧，却无法找到正确的剧集该怎么办？于是 Polycarp 现在想计算他将不得不使用其他方法搜索...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of seasons.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ denotes the number of episodes in season $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments