SEQUENCE

دنباله‌ی اعداد $a_1,a_2,\cdots,a_n$ را در نظر بگیرید. این دنباله $q$ بار تغییر می‌کند. هر تغییر را می‌توان به صورت $(p,x)$ نمایش داد به این معنا که عضو $p$ ام دنباله بعد از تغییر برابر با $x$ می‌شود. حال شما باید برنامه‌ای بنویسید که بعد از هر تغییر کمترین عدد صحیح و نامنفی $t$ را پیدا کند به طوری‌که دنباله‌ی $a_1 \oplus t, a_2 \oplus t, \cdots, a_n \oplus t$ دارای کمترین تعداد نابه‌جایی باشد. برنامه‌ی شما باید این مقدار $t$ و تعداد نابجایی‌ها، در دنباله‌ی تولید شده توسط آن را، در خروجی چاپ کند.

علامت $\oplus$ نشان‌دهنده‌ی عملگر $\mathrm{xor}$است. در یک دنباله‌ی دلخواه از اعداد مانند $c_1,c_2,\cdots,c_n$ جفت $(i,j)$ یک نابجایی است اگر و فقط اگر $i<j$ و $c_i > c_j$ باشد.

در سطر اول ورودی دو عدد طبیعی $n$، طول دنباله‌ی ورودی، و $q$، تعداد تغییر‌های دنباله، آمده است.

سطر دوم شامل $n$ عدد صحیح $a_1,a_2,\cdots,a_n$ است.

در هر یک از $q$ سطر بعدی به ترتیب دو عدد صحیح $p$ و $x$ آمده است که به معنای تغییر عضو $p$ ام دنباله به $x$ است.

خروجی شامل $q$ سطر است که در $i$ امین $(1\leq i\leq q)$ سطر از آن، پاسخ مسئله بعد از $i$‌ تغییر اول آمده است.

• زیرمسئله اول (۱۳ نمره): $n,q\leq 1000$
• زیرمسئله دوم (۱۹ نمره): $q=1$
• زیرمسئله سوم (۴۹ نمره): $n,q\leq 10^{4}$
• زیرمسئله چهارم (۱۹ نمره): بدون محدودیت اضافی

• $1\leq n,q\leq 5\times 10^{4}$
• $0\leq a_i, x< 2^{30}$
• $1\leq p\leq n$

در ورودی نمونه‌ی اول، وضعیت دنباله بعد از هر تغییر به صورت زیر بررسی شده است:

• بعد از تغییر اول: در این صورت دنباله‌ی اولیه به $1,1,0,0$ تبدیل می‌شود. در این حالت در صورتی که به جای $t$، عدد $1$ قرار دهیم، به دنباله‌ی $0,0,1,1$ می‌رسیم که تعداد نابجایی‌های آن صفر است. در صورتی که $t$ برابر با $0$ باشد، دنباله تغییر نمی‌کند و دارای چهار نابجایی است، بنابراین $t=1$ بهتر است. با توجه به این‌که به ازای $t=1$ تعداد نابجایی‌ها صفر است، بنابراین به ازای $t$‌های بزرگ‌تر تعداد نابجایی‌ها کم‌تر نیست. پس پاسخ همان $t=1$ است.
• یعد از تغییر دوم: در این صورت به دنباله‌ی $1,1,1,0$ می‌رسیم. در این حالت در صورتی که به جای $t$، عدد $1$ قرار دهیم، به دنباله‌ی $0,0,0,1$می‌رسیم که تعداد نابجایی‌های ان صفر است. در صورتی که $t=0$ باشد، دنباله تغییر نمی‌کند و بنابراین تعداد نابجایی‌های آن برابر با $3$ است. با استدلالی مشابه حالت قبلی، $t=1$ پاسخ مورد نظر است.
• بعد از تغییر سوم: در این صورت به دنباله‌ی $0,1,1,0$ می‌رسیم. در صورتی که $t=0$ باشد، تعداد نابجایی‌ها برابر با $2$ است و در صورتی که $t=1$ باشد نیز تعداد نابجایی‌ها برابر با $2$ است. می‌توان ثابت کرد که به ازای $t$‌های بزرگ‌تر از $1$ نیز تعداد نابجایی‌ها کم‌تر از $2$‌ نمی‌شود. با توجه به این‌که کوچک‌ترین $t$ در بین‌ آن‌هایی که نابجایی را کمینه می‌کنند باید به عنوان پاسخ در نظر گرفته شود، بنابراین پاسخ مسئله برابر با $0$‌ است.

• سوال بعد
• سوال قبل