{"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\u003eKevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. Each character of Kevin\u0027s string represents Kevin\u0027s score on one of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e questions of the olympiad—\u003cspan class\u003d\"tex-font-style-tt\"\u003e\u00271\u0027\u003c/span\u003e for a correctly identified cow and \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u00270\u0027\u003c/span\u003e otherwise.\u003c/p\u003e\u003cp\u003eHowever, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define an \u003cspan class\u003d\"tex-font-style-underline\"\u003ealternating subsequence\u003c/span\u003e of a string as a \u003cspan class\u003d\"tex-font-style-bf\"\u003enot-necessarily contiguous\u003c/span\u003e subsequence where no two consecutive elements are equal. For example, \u003cspan class\u003d\"tex-span\"\u003e{0, 1, 0, 1}\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e{1, 0, 1}\u003c/span\u003e, and \u003cspan class\u003d\"tex-span\"\u003e{1, 0, 1, 0}\u003c/span\u003e are alternating sequences, while \u003cspan class\u003d\"tex-span\"\u003e{1, 0, 0}\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e{0, 1, 0, 1, 1}\u003c/span\u003e are not.\u003c/p\u003e\u003cp\u003eKevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a \u003cspan class\u003d\"tex-font-style-bf\"\u003econtiguous\u003c/span\u003e non-empty substring of his score and change all \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u00270\u0027\u003c/span\u003es in that substring to \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u00271\u0027\u003c/span\u003es and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains the number of questions on the olympiad \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 ≤ 100 000\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe following line contains a binary string of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e representing Kevin\u0027s results on the USAICO. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.\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\u003e8\n10000011\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\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\u003e2\n01\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":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample, Kevin can flip the bolded substring \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e100\u003c/span\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e00\u003c/span\u003e\u003cspan class\u003d\"tex-font-style-tt\"\u003e011\u003c/span\u003e\u0027 and turn his string into \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e10011011\u003c/span\u003e\u0027, which has an alternating subsequence of length 5: \u0027\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e01\u003c/span\u003e\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e01\u003c/span\u003e\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e\u0027.\u003c/p\u003e\u003cp\u003eIn the second sample, Kevin can flip the entire string and still have the same score.\u003c/p\u003e"}}]}