{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eOne fine day Sasha went to the park for a walk. In the park, he saw that his favorite bench is occupied, and he had to sit down on the neighboring one. He sat down and began to listen to the silence. Suddenly, he got a question: what if in different parts of the park, the silence sounds in different ways? So it was. Let\u0027s divide the park into $$$1 \\times 1$$$ meter squares and call them \u003cspan class\u003d\"tex-font-style-it\"\u003ecells\u003c/span\u003e, and numerate rows from $$$1$$$ to $$$n$$$ from up to down, and columns from $$$1$$$ to $$$m$$$ from left to right. And now, every cell can be described with a pair of two integers $$$(x, y)$$$, where $$$x$$$\u0026nbsp;— the number of the row, and $$$y$$$\u0026nbsp;— the number of the column. Sasha knows that the level of silence in the cell $$$(i, j)$$$ equals to $$$f_{i,j}$$$, and all $$$f_{i,j}$$$ form a permutation of numbers from $$$1$$$ to $$$n \\cdot m$$$. Sasha decided to count, how many are there \u003cspan class\u003d\"tex-font-style-it\"\u003epleasant\u003c/span\u003e segments of silence?\u003c/p\u003e\u003cp\u003eLet\u0027s take some segment $$$[l \\ldots r]$$$. Denote $$$S$$$ as the set of cells $$$(i, j)$$$ that $$$l \\le f_{i,j} \\le r$$$. Then, the segment of silence $$$[l \\ldots r]$$$ is \u003cspan class\u003d\"tex-font-style-it\"\u003epleasant\u003c/span\u003e if there is only \u003cspan class\u003d\"tex-font-style-bf\"\u003eone simple\u003c/span\u003e path between every pair of cells from $$$S$$$ (path can\u0027t contain cells, which are not in $$$S$$$). In other words, set $$$S$$$ should look like a tree on a plain. Sasha has done this task pretty quickly, and called the algorithm\u0026nbsp;— \"algorithm of silence\u0027s sounds\".\u003c/p\u003e\u003cp\u003eTime passed, and the only thing left from the algorithm is a legend. To prove the truthfulness of this story, you have to help Sasha and to find the number of \u003cspan class\u003d\"tex-font-style-bf\"\u003edifferent\u003c/span\u003e \u003cspan class\u003d\"tex-font-style-it\"\u003epleasant\u003c/span\u003e segments of silence. Two segments $$$[l_1 \\ldots r_1]$$$, $$$[l_2 \\ldots r_2]$$$ are different, if $$$l_1 \\neq l_2$$$ or $$$r_1 \\neq r_2$$$ or both at the same time.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \\le n, m \\le 1000$$$, $$$1 \\le n \\cdot m \\le 2 \\cdot 10^5$$$)\u0026nbsp;— the size of the park.\u003c/p\u003e\u003cp\u003eEach from next $$$n$$$ lines contains $$$m$$$ integers $$$f_{i,j}$$$ ($$$1 \\le f_{i,j} \\le n \\cdot m$$$)\u0026nbsp;— the level of silence in the cell with number $$$(i, j)$$$.\u003c/p\u003e\u003cp\u003eIt is guaranteed, that all $$$f_{i,j}$$$ are different.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint one integer\u0026nbsp;— the number of \u003cspan class\u003d\"tex-font-style-it\"\u003epleasant\u003c/span\u003e segments of silence.\u003c/p\u003e"}},{"title":"Examples","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\u003e1 5\n1 2 3 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e2 3\n1 2 3\n4 5 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e4 4\n4 3 2 16\n1 13 14 15\n5 7 8 12\n6 11 9 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e50\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example, all segments of silence are \u003cspan class\u003d\"tex-font-style-it\"\u003epleasant\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second example, \u003cspan class\u003d\"tex-font-style-it\"\u003epleasant\u003c/span\u003e segments of silence are the following:\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/e7364d0baab6fe9a0b8b905ab385fbcf?v\u003d1719239419\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e"}}]}