{"raw_statement":[{"iden":"problem statement","content":"For positive integers $h$ and $w$, let $(h,w)$ denote a rectangle with height $h$ and width $w$. In this problem, we do not consider rotating the rectangles, and the rectangles $(h,w)$ and $(w,h)$ are distinguished when $h \\neq w$.\nA sequence of rectangles $((h_1,w_1),(h_2,w_2),\\dots ,(h_n,w_n))$ is called a **rectangle generation sequence** if there exists a method that successfully follows the steps below:\n\n*   Let the rectangle $X$ be $(h_1,w_1)$. Hereafter, let $H$ and $W$ respectively denote the height and width of the rectangle $X$ at each step.\n*   For $i=2,3,\\dots ,n$, perform one of the following operations. If neither can be performed, the procedure unsuccessfully terminates.\n    *   If the height of $X$ is equal to $h_i$, attach the rectangle $(h_i,w_i)$ horizontally to $X$. Formally, if $H=h_i$ at that time, replace $X$ with the rectangle $(H,W+w_i)$.\n    *   If the width of $X$ is equal to $w_i$, attach the rectangle $(h_i,w_i)$ vertically to $X$. Formally, if $W=w_i$ at that time, replace $X$ with the rectangle $(H+h_i,W)$.\n*   If the above series of operations does not fail, the procedure successfully terminates.\n\n* * *\n\nYou are given $N$ rectangles. The $i$\\-th rectangle has a height of $H_i$ and a width of $W_i$.\nFind the number of pairs of positive integers $(l,r)$ that satisfy $1 \\le l \\le r \\le N$ and the following condition:\n\n*   The sequence of rectangles $((H_l,W_l),(H_{l+1},W_{l+1}),\\dots ,(H_r,W_r))$ is a rectangle generation sequence."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 3 \\times 10^5$\n*   $1 \\leq H_i, W_i \\leq 10^6$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$H_1$ $W_1$\n$H_2$ $W_2$\n$\\vdots$\n$H_N$ $W_N$"},{"iden":"sample input 1","content":"4\n1 2\n1 3\n2 3\n3 1"},{"iden":"sample output 1","content":"7\n\nThe pairs $(l,r)$ that satisfy the condition are $(1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(4,4)$; there are seven.\nFor example, for $(l,r)=(2,4)$, the procedure succeeds if the first attachment is done vertically and the second is done horizontally."},{"iden":"sample input 2","content":"5\n2 1\n2 1\n1 2\n3 2\n1 4"},{"iden":"sample output 2","content":"10"},{"iden":"sample input 3","content":"1\n1000000 1000000"},{"iden":"sample output 3","content":"1"},{"iden":"sample input 4","content":"10\n1 1\n1 1\n1 1\n1 1\n1 1\n1 1\n1 1\n1 1\n1 1\n1 1"},{"iden":"sample output 4","content":"55"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}