{"raw_statement":[{"iden":"statement","content":"_Hands that shed innocent blood!_\n\nThere are _n_ guilty people in a line, the _i_\\-th of them holds a claw with length _L__i_. The bell rings and every person kills some of people in front of him. All people kill others at the same time. Namely, the _i_\\-th person kills the _j_\\-th person if and only if _j_ < _i_ and _j_ ≥ _i_ - _L__i_.\n\nYou are given lengths of the claws. You need to find the total number of alive people after the bell rings."},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 106) — the number of guilty people.\n\nSecond line contains _n_ space-separated integers _L_1, _L_2, ..., _L__n_ (0 ≤ _L__i_ ≤ 109), where _L__i_ is the length of the _i_\\-th person's claw."},{"iden":"output","content":"Print one integer — the total number of alive people after the bell rings."},{"iden":"examples","content":"Input\n\n4\n0 1 0 10\n\nOutput\n\n1\n\nInput\n\n2\n0 0\n\nOutput\n\n2\n\nInput\n\n10\n1 1 3 0 0 0 2 1 0 3\n\nOutput\n\n3"},{"iden":"note","content":"In first sample the last person kills everyone in front of him."}],"translated_statement":[{"iden":"statement","content":"_Hands that shed innocent blood!_\n\n有 #cf_span[n] 个有罪的人排成一列，第 #cf_span[i] 个人手持一把长度为 #cf_span[Li] 的爪子。钟声响起，每个人都会杀死他前面的一些人。所有人同时行动。具体来说，第 #cf_span[i] 个人会杀死第 #cf_span[j] 个人，当且仅当 #cf_span[j < i] 且 #cf_span[j ≥ i - Li]。\n\n给你每个人的爪子长度，你需要求出钟声响起后仍然活着的人的总数。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 106]) —— 有罪之人的数量。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[L1, L2, ..., Ln] (#cf_span[0 ≤ Li ≤ 109])，其中 #cf_span[Li] 是第 #cf_span[i] 个人的爪子长度。\n\n请输出一个整数——钟声响起后仍然活着的人的总数。\n\n在第一个样例中，最后一个人杀死了他前面的所有人。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 106]) —— 有罪之人的数量。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[L1, L2, ..., Ln] (#cf_span[0 ≤ Li ≤ 109])，其中 #cf_span[Li] 是第 #cf_span[i] 个人的爪子长度。"},{"iden":"output","content":"请输出一个整数——钟声响起后仍然活着的人的总数。"},{"iden":"examples","content":"输入\n4\n0 1 0 10\n输出\n1\n\n输入\n2\n0 0\n输出\n2\n\n输入\n10\n1 1 3 0 0 0 2 1 0 3\n输出\n3"},{"iden":"note","content":"在第一个样例中，最后一个人杀死了他前面的所有人。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be the number of people, indexed from $ 1 $ to $ n $.  \nLet $ L_i $ denote the claw length of the $ i $-th person.\n\nFor each person $ i $, they kill all persons $ j $ such that:\n$$\nj < i \\quad \\text{and} \\quad j \\geq i - L_i\n$$\n\nThat is, person $ i $ kills all people in the range $ [\\max(1, i - L_i), i - 1] $.\n\nA person $ j $ is alive after the bell rings if and only if **no** person $ i > j $ kills them, i.e., for all $ i > j $, it is **not** true that $ j \\in [i - L_i, i - 1] $.\n\nEquivalently, person $ j $ is killed if there exists some $ i > j $ such that:\n$$\ni - L_i \\leq j < i\n$$\n\nThus, person $ j $ is **alive** if and only if:\n$$\n\\forall i > j, \\quad j < i - L_i \\quad \\text{or} \\quad j \\geq i\n$$\nBut since $ j < i $ always holds for $ i > j $, the condition simplifies to:\n$$\n\\forall i > j, \\quad j < i - L_i\n\\quad \\iff \\quad\n\\forall i > j, \\quad L_i < i - j\n$$\n\nAlternatively, person $ j $ is **killed** if:\n$$\n\\exists i > j \\text{ such that } L_i \\geq i - j\n$$\n\nSo, person $ j $ is alive if and only if:\n$$\n\\max_{i > j} (i - L_i) > j\n$$\nis **false** — that is, if:\n$$\n\\max_{i > j} (i - L_i) \\leq j\n$$\n\nBut more directly:  \nDefine for each $ i $, the leftmost index that person $ i $ can kill: $ \\ell_i = \\max(1, i - L_i) $.  \nThen person $ j $ is killed if there exists $ i > j $ such that $ \\ell_i \\leq j $.\n\nSo, person $ j $ is alive if and only if:\n$$\n\\min_{i > j} \\ell_i > j\n$$\n\nThus, the number of alive people is:\n$$\n\\left| \\left\\{ j \\in \\{1, 2, \\dots, n\\} \\mid \\min_{i > j} \\max(1, i - L_i) > j \\right\\} \\right|\n$$\n\nNote: For $ j = n $, there is no $ i > j $, so the minimum over an empty set is $ \\infty $, so person $ n $ is always alive.\n\nWe can compute this efficiently by processing from right to left.\n\nLet $ R_j = \\min_{i > j} \\max(1, i - L_i) $, with $ R_n = \\infty $.\n\nThen:\n- Person $ j $ is alive $ \\iff R_j > j $\n\nWe can compute $ R_j $ iteratively from $ j = n-1 $ down to $ 1 $:\n$$\nR_j = \\min\\left( \\max(1, j+1 - L_{j+1}), R_{j+1} \\right)\n$$\n\n**Final formal statement:**\n\nLet $ n \\in \\mathbb{N} $, $ L_1, \\dots, L_n \\in \\mathbb{Z}_{\\geq 0} $.  \nDefine $ \\ell_i = \\max(1, i - L_i) $ for $ i = 1, \\dots, n $.  \nDefine $ R_n = \\infty $, and for $ j = n-1, \\dots, 1 $:\n$$\nR_j = \\min(\\ell_{j+1}, R_{j+1})\n$$\n\nThen the number of alive people is:\n$$\n\\sum_{j=1}^n \\mathbf{1}_{\\{R_j > j\\}}\n$$","simple_statement":null,"has_page_source":false}