{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer\u0027s inputs. \u003cbr\u003e\u003cbr\u003eMaximizer is implemented as a pipeline of sorters Sorter(i1, j1), ... , Sorter(ik, jk). Each sorter has n inputs and n outputs. Sorter(i, j) sorts values on inputs i, i+1,... , j in non-decreasing order and lets the other inputs pass through unchanged. The n-th output of the last sorter is the output of the Maximizer. \u003cbr\u003e\u003cbr\u003eAn intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing correct results for all possible combinations of input values? \u003cbr\u003e\u003cbr\u003eTask\u003cbr\u003eWrite a program that:\u003cbr\u003e\u003cbr\u003ereads a description of a Maximizer, i.e. the initial sequence of sorters in the pipeline, \u003cbr\u003ecomputes the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible input data, \u003cbr\u003ewrites the result. \u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains two integers n and m (2 \u0026lt;\u003d n \u0026lt;\u003d 50000, 1 \u0026lt;\u003d m \u0026lt;\u003d 500000) separated by a single space. Integer n is the number of inputs and integer m is the number of sorters in the pipeline. The initial sequence of sorters is described in the next m lines. The k-th of these lines contains the parameters of the k-th sorter: two integers ik and jk (1 \u0026lt;\u003d ik \u0026lt; jk \u0026lt;\u003d n) separated by a single space. "}},{"title":"Output","value":{"format":"HTML","content":"The output consists of only one line containing an integer equal to the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible data. "}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e40 6\r\n20 30\r\n1 10\r\n10 20\r\n20 30\r\n15 25\r\n30 40\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"Huge input data, scanf is recommended."}}]}