{"problem":{"name":"LIS 2","description":{"content":"We have a sequence $X$, which is initially empty.   Takahashi has performed the following operation for $i=1,2,\\ldots,N$ in this order. *   Append $l_i,l_i+1,\\ldots,r_i$ in this order to the end of $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc159_d"},"statements":[{"statement_type":"Markdown","content":"We have a sequence $X$, which is initially empty.  \nTakahashi has performed the following operation for $i=1,2,\\ldots,N$ in this order.\n\n*   Append $l_i,l_i+1,\\ldots,r_i$ in this order to the end of $X$.\n\nFind the greatest length of a strictly increasing subsequence of the final $X$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq l_i \\leq r_i \\leq 10^9$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$l_1$ $r_1$\n$\\vdots$\n$l_{N}$ $r_{N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc159_d","tags":[],"sample_group":[["4\n1 1\n2 4\n10 11\n7 10","8\n\nThe final $X$ is $(1,2,3,4,10,11,7,8,9,10)$.  \nThe $1$\\-st, $2$\\-nd, $3$\\-rd, $4$\\-th, $7$\\-th, $8$\\-th, $9$\\-th, and $10$\\-th elements form a strictly increasing subsequence with the greatest length."],["4\n1 1\n1 1\n1 1\n1 1","1\n\nThe final $X$ is $(1,1,1,1)$."],["1\n1 1000000000","1000000000"]],"created_at":"2026-03-03 11:01:14"}}