{"trustable":false,"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":"You have a row of n colored blocks numbered from 1 to n from left to right. The i-th block initially has the color $c_i$.\n\u003cbr\u003e\u003cbr\u003e\nWhen $c_i \u003d c_j \u003d c_k$, and $i \u003c k \u003c j$, then the $i$-th and $j$-th blocks belong to the same connected component, that is, the colors of the blocks from the $i$-th to the $j$-th are the same and belong to the same connected component.\n\u003cbr\u003e\u003cbr\u003e\nFor example, the row of colored blocks [3,3,3] has 1 connected component, while another row of colored blocks [5,2,4,4] has 3 connected components.\n\u003cbr\u003e\u003cbr\u003e\n\nAt the beginning, you can choose any starting block (this does not count as one round yet).\n\u003cbr\u003e\u003cbr\u003e\nYou can do the following operations several times:\n\u003cbr\u003e\u003cbr\u003e\nThen, in each round of the game, change the color of the connected component containing the starting block to any color.\n\u003cbr\u003e\u003cbr\u003e\n\nWhat are the minimum rounds required to turn the entire row of blocks into the same color?"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$n$$$ ($$$1 \\le n \\le 5000$$$)\u0026nbsp;— the number of squares.\u003c/p\u003e\n\u003cp\u003eThe second line contains integers $$$c_1, c_2, \\ldots, c_n$$$ ($$$1 \\le c_i \\le 5000$$$)\u0026nbsp;— the initial colors of the squares.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer\u0026nbsp;— the minimum number of the turns needed.\u003c/p\u003e"}},{"title":"Sample 1","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\n5 2 2 1\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":"Sample 2","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\u003e8\n4 5 2 2 1 3 5 5\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":"Sample 3","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\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\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\u003eIn the first example, a possible way to achieve an optimal answer is to pick square with index $$$2$$$ as the starting square and then play as follows:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e$$$[5, 2, 2, 1]$$$\u003c/li\u003e\n \u003cli\u003e$$$[5, 5, 5, 1]$$$\u003c/li\u003e\n \u003cli\u003e$$$[1, 1, 1, 1]$$$\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eIn the second example, a possible way to achieve an optimal answer is to pick square with index $$$5$$$ as the starting square and then perform recoloring into colors $$$2, 3, 5, 4$$$ in that order.\u003c/p\u003e\n\u003cp\u003eIn the third example, the line already consists of one color only.\u003c/p\u003e"}}]}