{"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\u003eSanta Claus has Robot which lives on the infinite grid and can move \u003cspan class\u003d\"tex-font-style-bf\"\u003ealong its lines\u003c/span\u003e. He can also, having a sequence of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e points \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e with integer coordinates, do the following: denote its initial location by \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e\u003c/span\u003e. First, the robot will move from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e along one of the shortest paths between them (please notice that since the robot moves only along the grid lines, there can be several shortest paths). Then, after it reaches \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e, it\u0027ll move to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e, again, choosing one of the shortest ways, then to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e3\u003c/sub\u003e\u003c/span\u003e, and so on, until he has visited all points in the given order. Some of the points in the sequence may coincide, in that case Robot will visit that point several times according to the sequence order.\u003c/p\u003e\u003cp\u003eWhile Santa was away, someone gave a sequence of points to Robot. This sequence is now lost, but Robot saved the protocol of its unit movements. Please, find the minimum possible length of the sequence.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains the only positive integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) which equals the number of unit segments the robot traveled. The second line contains the movements protocol, which consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e letters, each being equal either \u003cspan class\u003d\"tex-font-style-tt\"\u003eL\u003c/span\u003e, or \u003cspan class\u003d\"tex-font-style-tt\"\u003eR\u003c/span\u003e, or \u003cspan class\u003d\"tex-font-style-tt\"\u003eU\u003c/span\u003e, or \u003cspan class\u003d\"tex-font-style-tt\"\u003eD\u003c/span\u003e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e-th letter stands for the direction which Robot traveled the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e-th unit segment in: \u003cspan class\u003d\"tex-font-style-tt\"\u003eL\u003c/span\u003e means that it moved to the left, \u003cspan class\u003d\"tex-font-style-tt\"\u003eR\u003c/span\u003e\u0026nbsp;— to the right, \u003cspan class\u003d\"tex-font-style-tt\"\u003eU\u003c/span\u003e\u0026nbsp;— to the top and \u003cspan class\u003d\"tex-font-style-tt\"\u003eD\u003c/span\u003e\u0026nbsp;— to the bottom. Have a look at the illustrations for better explanation.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe only line of input should contain the minimum possible length of the sequence.\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\u003e4\nRURD\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\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\u003e6\nRRULDD\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\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\u003e26\nRRRULURURUULULLLDLDDRDRDLD\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\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\u003e3\nRLL\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\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\nLRLR\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\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\u003eThe illustrations to the first three tests are given below.\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/727e24f6c4818b929df9ab8651520454?v\u003d1719539502\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/346a99bdaead415743776068d913069a?v\u003d1719539502\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/d58422f24d649ff7a66fd3316c6c729a?v\u003d1719539502\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eThe last example illustrates that each point in the sequence should be counted as many times as it is presented in the sequence.\u003c/p\u003e"}}]}