{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eMatryoshkas are sets of traditional Russian wooden dolls of\n decreasing size placed one inside the other. A matryoshka doll\n can be opened to reveal a smaller figure of the same sort\n inside, which has, in turn, another figure inside, and so\n on.\u003c/p\u003e\n\n \u003cdiv style\u003d\"width:40.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/e6825d20f4a992dcf3cc716eedd1ab04?v\u003d1715457660\" alt\u003d\"/problems/matryoshka/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eThe Russian Matryoshka Museum recently exhibited a\n collection of similarly designed matryoshka sets, differing\n only in the number of nested dolls in each set. Unfortunately,\n some over-zealous (and obviously unsupervised) children\n separated these sets, placing all the individual dolls in a\n row. There are \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e dolls\n in the row, each with an integer size. You need to reassemble\n the matryoshka sets, knowing neither the number of sets nor the\n number of dolls in each set. You know only that every complete\n set consists of dolls with consecutive sizes from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to some number \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e, which may vary between the\n different sets.\n\n \u003cp\u003eWhen reassembling the sets, you must follow these rules:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eYou can put a doll or a nested group of dolls only\n inside a larger doll.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eYou can combine two groups of dolls only if they are\n adjacent in the row.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eOnce a doll becomes a member of a group, it cannot be\n transferred to another group or permanently separated from\n the group. It can be temporarily separated only when\n combining two groups.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eYour time is valuable, and you want to do this reassembly\n process as quickly as possible. The only time-consuming part of\n this task is opening and subsequently closing a doll, so you\n want to minimize how often you do this. For example, the\n minimum number of openings (and subsequent closings) when\n combining group [1, 2, 6] with the group [4] is two, since you\n have to open the dolls with sizes 6 and 4. When combining group\n [1, 2, 5] with the group [3, 4], you need to perform three\n openings.\u003c/p\u003e\n\n \u003cp\u003eWrite a program to calculate the minimum number of openings\n required to combine all disassembled matryoshka sets.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single test case. A test case\n consists of two lines. The first line contains one integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le n \\le 500$\u003c/span\u003e) representing the\n number of individual dolls in the row. The second line contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e positive integers\n specifying the sizes of the dolls in the order they appear in\n the row. Each size is between \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$500$\u003c/span\u003e inclusive.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay the minimum number of openings required when\n reassembling the matryoshka sets. If reassembling cannot be\n done (some of the kids might have been excessively zealous and\n taken some dolls), display the word \u003ctt class\u003d\"tt\"\u003eimpossible\u003c/tt\u003e.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e7\n1 2 3 2 4 1 3\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\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e7\n1 2 1 2 4 3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eimpossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}