{"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":"\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/5cd20661f9e89fd4dcca473e94f1887e?v\u003d1716048657\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eParis has been called \"ville lumière\" (city of lights) since the 17th century. It earned this nickname in part because of the many city lights illuminating famous sites such as monuments, statues, churches, or fountains.\u003c/p\u003e\u003cp\u003eThose public lights in Paris are numbered from $$$1$$$ to $$$N$$$ and are all on by default. A group of hackers has gained the capability to toggle groups of lights. Every time the hackers use their program, they cause a number $$$i$$$ (that they cannot control) to be sent to the system controlling the city lights. The lights numbered $$$i$$$, $$$2i$$$, $$$3i$$$, and so on (up to $$$N$$$) then change state instantly: lights that were on go off, and lights that were off go on.\u003c/p\u003e\u003cp\u003eDuring the night, the hackers use their programs $$$k$$$ times. What is the greatest number of lights that are simultaneously off at the same time?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input comprises several lines, each consisting of a single integer: \u003c/p\u003e\u003cul\u003e \u003cli\u003e The first line contains the number $$$N$$$ of lights. $$$1\\le N \\le 1000000$$$. \u003c/li\u003e\u003cli\u003e The second line contains the number $$$k$$$ of uses hackers\u0027s program. $$$1 \\le k \\le 100$$$. \u003c/li\u003e\u003cli\u003e The next $$$k$$$ lines contain a number $$$i$$$ sent to the system controlling the lights. $$$1 \\le i \\le N$$$. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output should consist of a single line, whose content is an integer, the greatest number of lights that are simultaneously off at the same time.\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\u003e10\n4\n6\n2\n1\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\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\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eSample Explanation:\u003c/span\u003e\u003c/p\u003e\u003cp\u003eWe start with a group of 10 lights which are all on. \u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/ac7a9a3708e3725e1471e5a5589c357c?v\u003d1716048657\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e The hackers send the number 6: light 6 is toggled. \u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/41b1b3403dc43e83db7d9b107ab1d8b1?v\u003d1716048657\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e They then send the number 2: lights 2, 4, 6, 8, and 10 are toggled. \u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/837f874477175e1f86bf34d20ea8dff4?v\u003d1716048657\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e The number 1 is then sent: all lights are toggled. \u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/4aedcc65c2404ac8359cc9511808f277?v\u003d1716048657\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e They end up sending the number 3: lights 3, 6, and 9 are toggled. \u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/c026b026d403960e20443e527529c96f?v\u003d1716048657\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e The maximum number of lights off at the same time was 6."}}]}