{"problem":{"name":"Insert 1, 2, 3, ...","description":{"content":"A sequence $a = (a_1, \\ldots, a_n)$ consisting of positive integers is said to be **generatable** when one can obtain $a$ by repeating the following operation on an empty sequence. *   Operation: Cho","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc063_b"},"statements":[{"statement_type":"Markdown","content":"A sequence $a = (a_1, \\ldots, a_n)$ consisting of positive integers is said to be **generatable** when one can obtain $a$ by repeating the following operation on an empty sequence.\n\n*   Operation: Choose a positive integer $k$, and insert $(1, 2, \\ldots, k-1, k)$ into some position in the sequence. More formally, for a sequence $a = (a_1, \\ldots, a_m)$, choose an integer $i$ such that $0\\leq i\\leq m$ and a positive integer $k$, and replace $a$ with $(a_1,\\ldots,a_{i}, 1, 2, \\ldots, k-1, k, a_{i+1}, \\ldots, a_m)$.\n\nFor instance, $a = (1,2,1,1,2,1,3,4,2,3)$ is generatable. Here is one way to generate it:\n$() \\to (\\boldsymbol{1,2}) \\to (1,2,\\boldsymbol{1,2,3}) \\to (1,2,1,\\boldsymbol{1,2,3,4},2,3) \\to (1,2,1,1,2,\\boldsymbol{1},3,4,2,3).$\n\n* * *\n\nYou are given a sequence $A = (A_1, \\ldots, A_N)$ consisting of positive integers. Find the number of pairs of integers $(L, R)$ such that:\n\n*   $1\\leq L\\leq R\\leq N$ and the contiguous subsequence $(A_L, \\ldots, A_R)$ is generatable.\n\n## Constraints\n\n*   $1\\leq N\\leq 5\\times 10^5$\n*   $1\\leq A_i\\leq N$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc063_b","tags":[],"sample_group":[["6\n1 2 1 2 1 3","11\n\nHere are the $11$ sought pairs:\n\n*   $(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (3,3), (3,4), (3,5), (3,6), (5,5).$"],["5\n1 1 1 1 1","15\n\nAll the contiguous subsequences are generatable."],["7\n1 2 1 2 1 3 4","13"]],"created_at":"2026-03-03 11:01:14"}}