{"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 vừa nhận được kết quả thất vọng của mình trong Cuộc thi Xác định Bò ở Mỹ (USAICO) dưới dạng một chuỗi nhị phân có độ dài \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. Mỗi ký tự trong chuỗi của Kevin đại diện cho số điểm của Kevin trên một trong \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e câu hỏi của cuộc thi - \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u00271\u0027\u003c/span\u003e cho việc xác định đúng một con bò và \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u00270\u0027\u003c/span\u003e cho trường hợp ngược lại.\u003c/p\u003e\u003cp\u003eTuy nhiên, mọi thứ vẫn chưa hết. Kevin là một người ủng hộ tư duy thay thế lớn và tin rằng điểm số của mình, thay vì là tổng số điểm, nên là độ dài của dãy con xen kẽ dài nhất của chuỗi của mình. Ở đây, chúng ta xác định một \u003cspan class\u003d\"tex-font-style-underline\"\u003edãy con xen kẽ\u003c/span\u003e của một chuỗi là một dãy con \u003cspan class\u003d\"tex-font-style-bf\"\u003ekhông nhất thiết liên tục\u003c/span\u003e trong đó không có hai phần tử liên tiếp giống nhau. Ví dụ, \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, và \u003cspan class\u003d\"tex-span\"\u003e{1, 0, 1, 0}\u003c/span\u003e là các dãy xen kẽ, trong khi \u003cspan class\u003d\"tex-span\"\u003e{1, 0, 0}\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e{0, 1, 0, 1, 1}\u003c/span\u003e không phải.\u003c/p\u003e\u003cp\u003eKevin, với tính cách lanh lợi như một quả bóng nhỏ, sẵn lòng hack vào cơ sở dữ liệu của USAICO để cải thiện điểm số của mình. Để tinh tế, anh quyết định rằng anh sẽ đảo chính xác một chuỗi con - nghĩa là, lấy một chuỗi con liên tục không rỗng của điểm số của mình và thay đổi tất cả các \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u00270\u0027\u003c/span\u003e trong chuỗi con đó thành \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u00271\u0027\u003c/span\u003e và ngược lại. Sau một phép toán như vậy, Kevin muốn biết độ dài của dãy con xen kẽ dài nhất có thể có của chuỗi của mình.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa số câu hỏi trong cuộc thi \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\u003eDòng tiếp theo chứa một chuỗi nhị phân có độ dài \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e đại diện cho kết quả của Kevin trong USAICO.\u003c/p\u003e"}},{"title":"Kết quả","value":{"format":"HTML","content":"\u003cp\u003eĐầu ra là một số nguyên duy nhất, độ dài của dãy con xen kẽ dài nhất mà Kevin có thể tạo ra trong chuỗi của mình sau khi đảo một chuỗi con.\u003c/p\u003e"}},{"title":"Ví dụ 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\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"}},{"title":"Ví dụ 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\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"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ đầu tiên, Kevin có thể đảo chuỗi con được in đậm \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 và biến chuỗi của mình thành \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e10011011\u003c/span\u003e\u0027, có một dãy xen kẽ có độ dài 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\u003eTrong ví dụ thứ hai, Kevin có thể đảo toàn bộ chuỗi và vẫn giữ nguyên điểm số.\u003c/p\u003e"}}]}