{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1\\leq N\\leq 5\\times 10^5$\n*   $1\\leq A_i\\leq N$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"6\n1 2 1 2 1 3"},{"iden":"sample output 1","content":"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).$"},{"iden":"sample input 2","content":"5\n1 1 1 1 1"},{"iden":"sample output 2","content":"15\n\nAll the contiguous subsequences are generatable."},{"iden":"sample input 3","content":"7\n1 2 1 2 1 3 4"},{"iden":"sample output 3","content":"13"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}