codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2156.md (44361B)


      1 Source: https://codeforces.com/blog/entry/147761
      2 
      3 ### Thank you for participating !
      4 
      5 Special Thanks to [hxu10](/profile/hxu10 "Master hxu10") for giving me the chance to write the editorial and for [maomao90](/profile/maomao90 "International Grandmaster maomao90") for enhancing the editorial !.
      6 
      7 Editorial of Problems E and F are written by hxu10, and the rest are written by me. I hope they're insightful and concise, please let me hear your opinion about it or any feedback in general đź’™.
      8 
      9 #### [2156A - Pizza Time](/contest/2156/problem/A "Codeforces Round 1061 (Div. 2)")
     10 
     11 **Hints**
     12 
     13 **Hint 1**
     14 
     15 Since $m_1 \le m_2$, the total number of slices Alice ate is always at least as much as the total number of slices Bob ate. What's optimal construction ?
     16 
     17 **Hint 2**
     18 
     19 We want to try to minimize the difference between the total number of slices Alice ate and the total number of slices Bob ate.
     20 
     21 **Hint 3**
     22 
     23 The optimal construction is to let both $m_1$ and $m_2$ to be equals to one. The sequence of operations, denoted by $(m_1, m_2, m_3)$, is as follows:
     24 
     25 $\displaystyle (1,1,n-2) \rightarrow (1,1,n-4) \rightarrow \ldots $
     26 
     27 **Solution**
     28 
     29 The general form of the sequence
     30 
     31 $\displaystyle (1,1,n-2) \rightarrow (1,1,n-4) \rightarrow \ldots $
     32 
     33 Note that we're considering the operations when $m_1 \le m_2 \le m_3$.
     34 
     35 Consider the case where $n$ is even:
     36 
     37 $\displaystyle (1,1,n-2) \rightarrow (1,1,n-4) \rightarrow \ldots \rightarrow (1,1,2)$
     38 
     39 The number of operations is the length of the sequence ${2,4,6,\ldots, 2(\frac{n}{2}-1)}$ which is $\frac{n}{2}-1$.
     40 
     41 Consider the case where $n$ is odd:
     42 
     43 $\displaystyle (1,1,n-2) \rightarrow (1,1,n-4) \rightarrow \ldots \rightarrow (1,1,1)$
     44 
     45 The number of operations is the length of the sequence ${1,3,5,7,\ldots, 2(\lfloor \frac{n}{2} \rfloor-1)+1}$
     46 
     47 By the representation of odd numbers we've ${2(0)+1,2(1)1+,\ldots, 2(\lfloor \frac{n}{2} \rfloor-1)+1}$ , which is equivalent to the length of ${0,1,2,\ldots, \frac{n-1}{2}-1}$ which gives the length of $\frac{n-1}{2}$.
     48 
     49 Both cases are equivalent to the close form
     50 
     51 $\left \lfloor \frac{n-1}{2} \right \rfloor$
     52 
     53 Complexity $\mathcal{O}(1)$.
     54 
     55 **Implementation 1 (MathModel)**
     56 
     57 ```
     58 from math import *
     59 
     60 def solve():
     61     n=int(input())
     62     print((n-1)//2)
     63 
     64 for _ in range(int(input())):
     65     solve()
     66 ```
     67 
     68 **Solution 2**
     69 
     70 It's possible to use fair split that's we use $\lfloor \frac{n}{3} \rfloor , \lfloor \frac{n}{3} \rfloor , \lfloor \frac{n}{3} \rfloor + n \bmod 3$ and keep simulating with $n=m_3$ on steps except the first step until you reach $m_2 \le 2$.
     71 
     72 Complexity $\mathcal{O}(\log_3(n))$
     73 
     74 **Implementation 2 (MathModel)**
     75 
     76 ```
     77 from math import *
     78 
     79 def solve():
     80     n=int(input())
     81     a,b,c=n//3,n//3,n//3+(n%3)
     82     ans=0
     83     while(n>2):
     84         ans+=n//3
     85         n=n//3+(n%3)
     86     print(ans)
     87 
     88 for _ in range(int(input())):
     89     solve()
     90 ```
     91 
     92 **Rate The Problem !**
     93 
     94 Great
     95 
     96 Good
     97 
     98 Neutral
     99 
    100 Bad
    101 
    102 Didn't Solve
    103 
    104 #### [2156B - Strange Machine](/contest/2156/problem/B "Codeforces Round 1061 (Div. 2)")
    105 
    106 **Hints**
    107 
    108 **Hint 1**
    109 
    110 What's the consuming part of processing the string of operations $s$ ?
    111 
    112 **Hint 2**
    113 
    114 If the string $s$ contained at least one $\mathtt{B}$ operation , What's the maximum count of iterations we're going to run so that $a=0$ ?
    115 
    116 **Hint 3**
    117 
    118 If the string $s$ contains $x$ copies of $\mathtt{B}$ then $a$ is guaranteed to be $a=0$ in at most $\mathcal{O}(\log_{2x} A)$ where $A=\max(a_1,a_2,\ldots ,a_n)$ , that's at most $\mathcal{O}(n \log_2 A) \sim \mathcal{O}(30n)$ operations are required .
    119 
    120 **Hint 4**
    121 
    122 How to manage too many appearances of $\mathtt{A}$ for efficiency ?
    123 
    124 **Hint 5**
    125 
    126 It's enough to handle the case where $\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$ that's the answer for query $a$ is $a$ because we're incrementing by 1 at each iteration ; otherwise the complexity becomes $\mathcal{O}(10^9q)$ for such cases which is slow. and the rest can be done in $\mathcal{O}(nq \log_2(10^9))$ which is safe according to the constraints.
    127 
    128 **Solution 1 : O(nq log A)**
    129 
    130 If you've one $\color{blue}{\mathtt{B}}$ in string $s$ , then you'll have to do operations in $\mathcal{O}(n\log_2(A))$ which is $\sim \mathcal{O}(20 \cdot 30)$ which is fine for $n \le 20$ and $\sum q \le 10^4$ , at worst case this is roughly $\mathcal{O}(6 \cdot 10^5)$ which is safe.
    131 
    132 If we've a string $s$ that's all $\color{red}{\mathtt{A}}$ i.e. :
    133 
    134 $s=\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$
    135 
    136 then answer is simply for each $a_i$ is $a_i$ itself because we cannot do anything except just subtracting by $1$ many times ; otherwise the complexity becomes $\mathcal{O}(10^9q)$ for such cases which is slow.
    137 
    138 Complexity $\mathcal{O}(nq \log_2(10^9))$.
    139 
    140 **Implementation 1 (MathModel)**
    141 
    142 ```
    143 def solve():
    144     n,q=map(int,input().split())
    145     s=input().strip()
    146     a=list(map(int,input().split()))
    147     A,B=s.count('A'),s.count('B')
    148     for i in range(q):
    149         if(B==0):
    150             print(a[i])
    151         else:
    152             ans=0
    153             while(a[i]):
    154                 for j in s:
    155                     if(a[i]==0):break
    156                     ans+=1
    157                     if(j=='A'):a[i]-=1
    158                     else: a[i]//=2
    159             print(ans)
    160 
    161 for _ in range(int(input())):
    162     solve()
    163 ```
    164 
    165 **Bonus Hints**
    166 
    167 **Hint 1**
    168 
    169 Compress the string $s$ into sequence of "Move Blocks" that's for $s=\mathtt{AABBBABAAA}$ the sequence of moves will be
    170 
    171 $\{[\mathtt{A},2],[\mathtt{B},3],[\mathtt{A},1],[\mathtt{B},1],[\mathtt{A},3]\}$
    172 
    173 **Hint 2**
    174 
    175 Be careful in simulation
    176 
    177 **Solution 2 (Bonus) : O(n+qlog^2 A)**
    178 
    179 **Observation :** The consuming part of processing the operations where a segment of $\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$ because we're processing one by one which is inefficient and answering query will take $\mathcal{O}(nq \log_2(10^9))$ , why ? , because processing $\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$ operation-by-operation is slow , for example consider the sequence $\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}} \color{blue}{\mathtt{B}}}_{}$
    180 
    181 This case will take $\mathcal{O}(nq \log_2(10^9))$ at worst case , which is inefficient.
    182 
    183 A good way to optimize is by compress the blocks of same type of operations as $(\mathrm{type},\mathrm{count})$ that way all long blocks of $\color{red}{\mathtt{A}}$ will be performed much faster , For blocks of $\color{blue}{\mathtt{B}}$ it's already fast to process them in order because of $\mathcal{O}(\log_2(a))$ and it reduces $a$ to $0$ in $\mathcal{O}(\log_2(10^9)) \sim 30$ at most , However compressing the operations is still better to compose the operations.
    184 
    185 That's we're going to process at most $\sim 60$ blocks , because if we started with $\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\ldots $ assuming $a=10^9$ , which is the worst case of the algorithm.
    186 
    187 Now after composing the blocks as $(\mathrm{type},\mathrm{count})$ , you should iterate through them :
    188 
    189 * If $s_i=\color{red}{\mathtt{A}}$ then we perform $a_i=a_i-\min(\mathrm{count},a_i)$
    190 * If $s_i=\color{blue}{\mathtt{B}}$ then we perform $\displaystyle a_i=\left \lfloor \frac{a_i}{\displaystyle 2^{\min(\text{count},\lceil \log_2(n) \rceil)}} \right \rfloor$
    191 
    192 make sure to update number of operations accordingly.
    193 
    194 Complexity $\sim \mathcal{O}(n+q \log^2(10^9))$.
    195 
    196 **Implementation 2 (MathModel)**
    197 
    198 ```
    199 def solve():
    200     n,q=map(int,input().split())
    201     s=input()
    202     a=list(map(int,input().split()))
    203     A=s.count('A')
    204     B=s.count('B')
    205     last=s[0]
    206     seq=[] 
    207     cur=1
    208     for i in range(1,n):
    209         if(s[i]==last): cur+=1
    210         else:
    211             seq.append([last,cur])
    212             cur=1
    213             last=s[i]
    214     if(cur!=0): seq.append([last,cur])
    215     if(B==0):
    216         for i in a: print(i)
    217     else:
    218         for i in range(q):
    219             ans=0
    220             while(a[i]>0):
    221                 for j in seq:
    222                     if(a[i]==0): break
    223                     if(j[0]=='A'):
    224                         mn=min(j[1],a[i])
    225                         ans+=mn
    226                         a[i]-=mn
    227                     else:
    228                         if a[i]==0: break
    229                         x=a[i]
    230                         p=0
    231                         while(x):
    232                             x//=2
    233                             p+=1
    234                         mn=min(p,j[1])
    235                         ans+=mn
    236                         a[i]//=(2**mn)
    237             print(ans)
    238 
    239 for _ in range(int(input())):
    240     solve()
    241 ```
    242 
    243 **Rate The Problem !**
    244 
    245 Great
    246 
    247 Good
    248 
    249 Neutral
    250 
    251 Bad
    252 
    253 Didn't Solve
    254 
    255 #### [2156C - Maximum GCD on Whiteboard](/contest/2156/problem/C "Codeforces Round 1061 (Div. 2)")
    256 
    257 **Hints**
    258 
    259 **Hint 1**
    260 
    261 You can do all the **Erase** operations before the **Split** operations.
    262 
    263 **Proof**
    264 
    265 Suppose there exists an optimal solution where you do an **Erase** operation on an element that was produced from a **Split** operation. You can instead do an **Erase** operation on the original element that it was being **Split** from, which will result in the whiteboard containing a subset of the elements in the optimal solution. Hence, it will have a beauty of at least as much as the optimal solution.
    266 
    267 **Hint 2**
    268 
    269 Fix a target gcd $g$. Which numbers can be made divisible by $g$ using the **Split** operation?
    270 
    271 **Hint 3**
    272 
    273 If $x$ is a multiple of $g$, we do not need any **Split** operation. If $x\ge 4g$, one split can result in two multiples of $g$ (discard the middle).
    274 
    275 **Proof**
    276 
    277 Split $x$ into $(g, g + x\bmod g, x - 2g - x\bmod g)$. Both $g$ and $x - 2g - x\bmod g$ are divisible by $g$.
    278 
    279 * If $x \lt 5g$, $x - 2g - x\bmod g = 2g$. $g + x\bmod g \le 2g = x - 2g - x\bmod g$, hence, $x_1 \le x_2 \le x_3$ is satisfied.
    280 * Otherwise, $x \ge 5g$. $x - 2g - x\bmod g \ge 5g - 2g - g = 2g \ge g + x\bmod g$, hence, $x_1 \le x_2 \le x_3$ is satisfied.
    281 
    282 **Hint 4**
    283 
    284 Conversely, if $x\lt 4g$ and $x$ is not divisible by $g$, you can’t make it good by splits → it must be erased.
    285 
    286 **Proof**
    287 
    288 We will prove this by strong induction.
    289 
    290 Let $P_i$ be the statement: $i$ cannot be made divisible by $g$ using any number of splits if $i \lt 4g$ and $i$ is not divisible by $g$.
    291 
    292 Base case: $P_1$ is true as $1$ cannot be split.
    293 
    294 Suppose $P_i$ is true for all $i \lt K$ for some $K \ge 2$. We will prove that $P_K$ is also true.
    295 
    296 If $K \ge 4g$ or $K$ is divisible by $g$, $P_K$ is vacuously true. From here on, we will assume that $K \lt 4g$ and $K$ is not divisible by $g$.
    297 
    298 Suppose we split $K$ into $x_1\le x_2\le x_3 \lt K$. If either $x_1$ or $x_3$ is not divisible by $g$, $P_{x_1}$ and $P_{x_3}$ implies that they can never be made divisible by $g$ using any number of splits. Hence, if we want to make $K$ divisible by $g$, $x_1$ and $x_3$ have to both be divisible by $g$.
    299 
    300 If $x_1 \ge 2g$, $x_3 \ge x_2 \ge x_1 \ge 2g$, which means that $K = x_1 + x_2 + x_3 \ge 2g + 2g + 2g = 6g$, which contradicts $K \lt 4g$. Hence, $x_1 = g$ is the only possibility.
    301 
    302 * If $x_3 = g$, $x_1 \le x_2 \le x_3 \rightarrow g \le x_2 \le g$. Hence, $x_2 = g$ as well, and $K = x_1 + x_2 + x_3 = g + g + g = 3g$, contradicting that $K$ is not divisible by $g$.
    303 * If $x_3 \ge 2g$, $K = x_1 + x_2 + x_3 \le g + g + 2g = 4g$, contradicting $K \lt 4g$.
    304 
    305 Hence, it is not posible to make $K$ divisible by $g$ using any number of splits.
    306 
    307 **Hint 5**
    308 
    309 So $g$ is good if
    310 
    311 $ \#\{x\ge 4g\}+\#\{x=g\}+\#\{x=2g\}+\#\{x=3g\}\ \ge\ n-k. $
    312 
    313 **Hint 6**
    314 
    315 Count with a frequency array / map and a prefix sum for $g=1,2,\ldots ,n$
    316 
    317 **Solution**
    318 
    319 We want the maximum gcd $g$ achievable after $\le k$ erases and any splits.
    320 
    321 For a fixed $g$, the elements that won’t consume an erase are:
    322 
    323 * all multiples of $g$ (already good), and
    324 * any $x\ge 4g$ (can be made good via one split using the construction in hint 3).
    325 
    326 Thus, the only "bad" numbers (that would have to be erased) are those with $x\lt 4g$ that are not multiples of $g$. Therefore $g$ is good if
    327 
    328 $\text{good}(g)=\#\{x\ge 4g\}+\#\{x=g\}+\#\{x=2g\}+\#\{x=3g\}\ \ge\ n-k.$
    329 
    330 Since $1\le a_i\le n$, precompute a frequency array and prefix sums $p[v]=\sum_{u\le v}f[u]$. Then
    331 
    332 $ \#\{x\ge 4g\}=n-p[\min(n,4g-1)]. $
    333 
    334 Iterate through $g=1,2,3,\ldots ,n$ and keep the largest good $g$.
    335 
    336 Complexity : $\mathcal{O}(n)$.
    337 
    338 **Implementation (MathModel)**
    339 
    340 ```
    341 #include <bits/stdc++.h>
    342 using namespace std;
    343 #define int long long
    344 
    345 void solve(){
    346   int n,k;cin>>n>>k;
    347   vector<int>a(n),mp(n+1),p(n+1);
    348   for(auto &i:a){
    349      cin>>i;
    350      mp[i]++;
    351   }
    352   for(int i=1;i<=n;i++){
    353       p[i]=p[i-1]+mp[i];
    354   }
    355   int ans=1;
    356   for(int g=1;g<=n;g++){
    357     int t=min(n,4*g-1);
    358     int good=n-p[t];
    359     if(g<=n)good+=mp[g];
    360     if(2*g<=n)good+=mp[2*g];
    361     if(3*g<=n)good+=mp[3*g];
    362     if(good>=n-k)ans=g;
    363   }
    364   cout<<ans<<"\n";
    365 }
    366 
    367 signed main(){
    368   ios::sync_with_stdio(0);
    369   cin.tie(0);
    370   int t;cin>>t;
    371   while(t--)solve();
    372 }
    373 ```
    374 
    375 **Rate The Problem !**
    376 
    377 Great
    378 
    379 Good
    380 
    381 Neutral
    382 
    383 Bad
    384 
    385 Didn't Solve
    386 
    387 #### [2156D - Find the Last Number](/contest/2156/problem/D "Codeforces Round 1061 (Div. 2)")
    388 
    389 **Hints**
    390 
    391 **Hint 1**
    392 
    393 We determine the $k$-th bit of $p_n$ for $k=0,1,\ldots,\lfloor\log_2 n\rfloor$.
    394 
    395 **Hint 2**
    396 
    397 Let $\text{bit}_k(i)$ denote the whether the $k$-th bit of $i$ is zero or one. How can we determine the $k$-th bit of $p_n$, i.e. $\text{bit}_k(p_n)$, from $\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$?
    398 
    399 **Hint 3**
    400 
    401 $ \sum_{k=0}^{\lfloor \log_2(n) \rfloor} \left \lceil \frac{n-1}{2^k} \right \rceil =n-1 + \left \lceil \frac{n-1}{2} \right \rceil + \left \lceil \frac{n-1}{4} \right \rceil + \left \lceil \frac{n-1}{8} \right \rceil+\ldots \lt 2n $
    402 
    403 How can we achieve this halving?
    404 
    405 **Solution**
    406 
    407 Recall from Hint 2 that $\text{bit}_k(i)$ is defined as $k$-th bit of the integer $i$. A naive solution using $n\log_2 n$ queries is as follows:
    408 
    409 * Compute $\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$ for all $k=0,1,\ldots,\lfloor\log_2 n\rfloor$.
    410 
    411   + $\text{bit}_k(p_i)$ can be computed with a single query $p_i \ \mathtt{AND} \ 2^k$ ($1\le i\le n - 1$).
    412 * If $\text{bit}_k(1) + \text{bit}_k(2) + \ldots + \text{bit}_k(n) = \text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$, it means that the $k$-th bit of $p_n$ is zero. Otherwise, it is one.
    413 
    414   + This works due to the fact that $\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1}) = \text{bit}_k(1) + \text{bit}_k(2) + \ldots + \text{bit}_k(n) - \text{bit}_k(p_n)$.
    415 
    416 To optimise this, we will half the search space after each step. Starting from $k = 0$, we still use $n - 1$ queries to calculate $\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$. After using this to determine the value of the $0$-th bit of $p_n$, we can discard all $p_i$ that has a different $0$-th bit from $p_n$.
    417 
    418 More formally, let $S_0$ denote the set of elements $i$ such that $i$ has the same $0$-th bit as $p_n$, and $P_0$ denote the set of elements $i$ ($1\le i\le n - 1$) such that $p_i$ has the same $0$-th bit as $p_n$. $\sum_{i\in P_0} \text{bit}_1(p_i) = \left(\sum_{i\in S_0} \text{bit}_1(i)\right) - \text{bit}_1(p_n)$, so the $1$-st bit of $p_n$ is zero if $\sum_{i\in P_0} \text{bit}_1(p_i) = \sum_{i\in S_0} \text{bit}_1(i)$.
    419 
    420 In general, we can let $S_k$ denote the set of elements $i$ such that $i$ has the same $0$-th, $1$-st, $\ldots$ , $k$-th bit as $p_n$, and $P_k$ denote the set of elements $i$ ($1\le i\le n - 1$) such that $p_i$ has the same $0$-th, $1$-st, $\ldots$ , $k$-th bit as $p_n$. Then, the $k$-th bit of $p_n$ is zero if $\sum_{i\in P_{k-1}} \text{bit}_k(p_i) = \sum_{i\in S_{k-1}} \text{bit}_k(i)$.
    421 
    422 Observe that $|P_k| \le \left\lceil \frac{|P_{k - 1}|}{2} \right\rceil$ for all $k\ge 1$. Hence, the total number of queries used is
    423 
    424 $n - 1 + \sum_{k=1}^{\lfloor \log_2(n) \rfloor} |P_{k - 1}| \le n-1 + \left \lceil \frac{n-1}{2} \right \rceil + \left \lceil \frac{n-1}{4} \right \rceil + \left \lceil \frac{n-1}{8} \right \rceil+\ldots \lt 2n$
    425 
    426 **Implementation (hxu10)**
    427 
    428 ```
    429 def query(index,num):
    430     print("?",index,num)
    431     return int(input())
    432 
    433 def main():
    434     n = int(input())
    435     rest = set()
    436     likely = set()
    437     for i in range(1,n):
    438         rest.add(i)
    439     for i in range(1,n+1):
    440         likely.add(i)
    441     D = len(bin(n)[2:])
    442     ans = 0
    443     for d in range(D):
    444         index_0 = set()
    445         index_1 = set() 
    446         likely_0 = set()
    447         likely_1 = set()
    448         for index in rest:
    449             res = query(index, 1<<d)   
    450             if res == 0:
    451                 index_0.add(index)
    452             else:
    453                 index_1.add(index)  
    454         zeros = 0
    455         ones = 0  
    456         for num in likely:
    457             if num & (1<<d):
    458                 ones += 1
    459                 likely_1.add(num)
    460             else:
    461                 zeros += 1
    462                 likely_0.add(num)
    463         if zeros == len(index_0):
    464             ans += 1 << d
    465             rest = index_1
    466             likely = likely_1
    467         elif ones == len(index_1):
    468             rest = index_0
    469             likely = likely_0
    470         else:
    471             print("Error")
    472             return 
    473     print("!",ans)
    474 
    475 T = int(input())
    476 t = 1
    477 while t <= T:
    478     main()
    479     t += 1
    480 ```
    481 
    482 **Rate The Problem !**
    483 
    484 Great
    485 
    486 Good
    487 
    488 Neutral
    489 
    490 Bad
    491 
    492 Didn't Solve
    493 
    494 #### [2156E - Best Time to Buy and Sell Stock](/contest/2156/problem/E "Codeforces Round 1061 (Div. 2)")
    495 
    496 **Hints**
    497 
    498 **Hint 1**
    499 
    500 Consider the simplified version of the game where Alex moves first.
    501 
    502 **Hint 1.1**
    503 
    504 Suppose Alex wants to ensure a beauty of at least $g$ (the goal), while Hao tries to keep it below $g$. Which indices should Alex lock to achieve this goal?
    505 
    506 **Hint 1.2**
    507 
    508 We can binary search on the goal $g$.
    509 
    510 **Hint 1.3**
    511 
    512 For a given $g$ and an index $i$, we define $f_g(a, i)$ as the number of indices $j\neq i$ satisfying $a_{\max(i, j)} - a_{\min(i, j)} \ge g$.
    513 
    514 If there exists an index $i$ such that $f_g(a, i) \ge 2$, then Alex can lock index $i$ on the first move. No matter which index Hao removes next, there will still exist at least one $j$ such that $|a_i - a_j| \ge g$. Thus, Alex can secure that pair and guarantee a beauty of at least $g$.
    515 
    516 **Hint 1.4**
    517 
    518 If $f_g(a, i) \le 1$ for all indices $i$, Alex cannot achieve his goal. Whichever index $i$ Alex locks first, Hao can remove the single $j$ such that $|a_i - a_j| \ge g$. Hence, Alex will never be able to lock two indices with a difference $\ge g$, and the resulting beauty will be strictly less than $g$.
    519 
    520 **Hint 2**
    521 
    522 Now return to the original problem, where Hao moves first.
    523 
    524 To keep the final beauty below $g$, Hao must remove an index such that after the removal, $f_g(a, i) \lt 2$ for all $i$. Otherwise, Alex will have a winning move as shown in Hint 1.3.
    525 
    526 **Hint 3**
    527 
    528 For each $i$, we only need to track whether $f_g(a, i)$ is $0$, $1$, $2$, or greater than $2$. This is because if there are any index $i$ with $f_g(a, i) \gt 2$, Hao has to remove index $i$ on his first move. Otherwise, we will have $f_g(a, i) \ge 2$ after Hao's first move, allowing Alex to have a beauty of at least $g$ as mentioned in Hint 2.
    529 
    530 This observation allows us to compute $f_g(a, i)$ efficiently.
    531 
    532 **Solution**
    533 
    534 Read the above hints before continuing.
    535 
    536 As noted in Hint 1.2, we can binary search on the target beauty $g$.
    537 
    538 For each index $1 \le i \le n$, recall that $f_g(a, i)$ is the number of indices $j\neq i$ satisfying $a_{\max(i, j)} - a_{\min(i, j)} \ge g$.
    539 
    540 As mentioned in Hint 3, we only care whether $f_g(a, i)$ is $0$, $1$, $2$, or greater than $2$. We iterate through $i = 1, \ldots, n$, and maintain the three smallest previous values $a_j$ (for $j \lt i$). For each of these, we check whether the condition holds and increment both $f_g(a, i)$ and $f_g(a, j)$ if it does. This leads to an $\mathcal{O}(3n) = \mathcal{O}(n)$ computation per $g$.
    541 
    542 We simulate each possible first move $p$ by Hao. Let array $b$ be array $a$ after removing index $p$. When Hao removes index $p$, only the $f_g(a, p)$ indices $q$ satisfying $|a_p - a_q| \ge g$ will have their $f_g(b, q) = f_g(a, q) - 1$, while all others remain unchanged.
    543 
    544 Hao succeeds in keeping the beauty below $g$ if and only if removing index $p$ results in all $f_g(b, i) \le 1$. Equivalently, the indices $q$ paired with $p$ must include all indices that initially had $f_g(a, i) = 2$.
    545 
    546 If no such removal $p$ works, Alex can achieve his goal of keeping the beauty at least $g$.
    547 
    548 Checking each first move $p$ requires $\mathcal{O}(f_g(a, p))$ time, and summing up over $\sum_{1\le p\le n} f_g(a, p) \le 2(3n) = \mathcal{O}(n)$ since we only maintain at most three previous values of $a_j$ (for $j \lt i$) during the calculation of $f_g(a, i)$.
    549 
    550 The total time complexity is $\mathcal{O}(n \log_2 10^9)$ since we perform a binary search over $g$ and compute $f_g(a, i)$ in linear time per iteration.
    551 
    552 **Implementation (hxu,PyPy)**
    553 
    554 ```
    555 def main():
    556     n = int(input())
    557     arr = list(map(int,input().split()))
    558 
    559     # calculate the number of j for each i that satisfy arr[max(i,j)] - arr[min(i,j)] >= target
    560     def measurecount(arr,target):
    561         m = len(arr)
    562         count = [0]*m
    563         minimum = []
    564         for i in range(m):
    565             for j in range(len(minimum)):
    566                 if minimum[j] + target <= arr[i]:
    567                     count[i] += 1
    568             minimum.append(arr[i])
    569             minimum.sort()
    570             if len(minimum) > 3:
    571                 minimum.pop()
    572         maximum = []
    573         for i in range(m-1,-1,-1):
    574             for j in range(len(maximum)):
    575                 if maximum[j] - target >= arr[i]:
    576                     count[i] += 1
    577             maximum.append(arr[i])
    578             maximum.sort(reverse=True)
    579             if len(maximum) > 3:
    580                 maximum.pop()
    581         return count
    582 
    583     # binary search to judge if we can find such pair
    584     def judge(target):
    585         count = measurecount(arr,target)
    586         if max(count) <= 1:
    587             return False
    588         pick = []
    589         if max(count) > 2:
    590             for i in range(n):
    591                 if count[i] > 2:
    592                     pick = [i]
    593                     break
    594         else:
    595             for i in range(n):
    596                 if count[i] != 2: 
    597                     continue 
    598                 for j in range(n):
    599                     if j==i: 
    600                         pick.append(j)
    601                     elif j < i and arr[j] + target <= arr[i]: 
    602                         pick.append(j)
    603                     elif j > i and arr[i] + target <= arr[j]:
    604                         pick.append(j)
    605                 break
    606 
    607         for p in pick:
    608             count2 = measurecount(arr[:p]+arr[p+1:], target)
    609             if max(count2) <= 1:
    610                 return False
    611         return True       
    612 
    613     front = -10**9 - 10
    614     rear = 10**9 + 10
    615     while front < rear:
    616         mid = front + (rear-front)//2
    617         res = judge(mid)
    618         if res:
    619             front = mid + 1
    620         else:
    621             rear = mid 
    622     ans = front - 1
    623     print(ans)
    624                        
    625 T = int(input())
    626 t = 1
    627 while t <= T:
    628     main()
    629     t += 1
    630 ```
    631 
    632 **Implementation (maomao90,C++)**
    633 
    634 ```
    635 #include "bits/stdc++.h"
    636 using namespace std;
    637  
    638 const int MAXN = 200005;
    639 const int INF = 1000000005;
    640  
    641 inline int fdiv(int num, int denom) {
    642   return num / denom - ((num ^ denom) < 0 && num % denom);
    643 }
    644 inline int cdiv(int num, int denom) { return fdiv(num + denom - 1, denom); }
    645  
    646 int t;
    647 int n;
    648 int a[MAXN];
    649  
    650 vector<int> adj[MAXN];
    651 void add_edge(int u, int v) {
    652   adj[u].push_back(v);
    653   adj[v].push_back(u);
    654 }
    655 bool check(int x) {
    656   for (int i = 1; i <= n; i++) {
    657     adj[i].clear();
    658   }
    659   set<pair<int, int>> st;
    660   for (int i = 1; i <= n; i++) {
    661     int cnt = 0;
    662     for (auto [prv, prv_id] : st) {
    663       if (a[i] - prv >= x) {
    664         add_edge(prv_id, i);
    665       }
    666     }
    667     st.insert({a[i], i});
    668     if ((int) st.size() > 3) {
    669         st.erase(prev(st.end()));
    670     }
    671   }
    672  
    673   int bad_cnt = 0;
    674   for (int i = 1; i <= n; i++) {
    675     if ((int)adj[i].size() >= 2) {
    676       bad_cnt++;
    677     }
    678   }
    679   for (int i = 1; i <= n; i++) {
    680     int delta = (int)adj[i].size() >= 2;
    681     for (int v : adj[i]) {
    682       if (adj[v].size() == 2) {
    683         delta++;
    684       }
    685     }
    686     if (delta == bad_cnt) {
    687       return false;
    688     }
    689   }
    690   return true;
    691 }
    692  
    693 int main() {
    694   cin >> t;
    695   while (t--) {
    696     cin >> n;
    697     for (int i = 1; i <= n; i++) {
    698       cin >> a[i];
    699     }
    700     int lo = -INF, hi = INF;
    701     while (lo < hi) {
    702       int mid = cdiv(lo + hi, 2);
    703       if (check(mid)) {
    704         lo = mid;
    705       } else {
    706         hi = mid - 1;
    707       }
    708     }
    709     cout << lo << '\n';
    710   }
    711   return 0;
    712 }
    713 ```
    714 
    715 **Rate The Problem !**
    716 
    717 Great
    718 
    719 Good
    720 
    721 Neutral
    722 
    723 Bad
    724 
    725 Didn't Solve
    726 
    727 #### [2156F1 - Strange Operation (Easy Version)](/contest/2156/problem/F1 "Codeforces Round 1061 (Div. 2)")
    728 
    729 **hxu10's Solution**
    730 
    731 **Hints**
    732 
    733 **Hint 1**
    734 
    735 What will the first element of permutation be for the final result?
    736 
    737 **Hint 2**
    738 
    739 If the first element is odd, we can always reduce it to $1$, otherwise, we can always reduce it to $2$.
    740 
    741 **Hint 3**
    742 
    743 If the first element is even, before reducing the first element to $2$, we must reduce some element to $1$ at first. Which one to choose?
    744 
    745 **Hint 4**
    746 
    747 You should choose the leftmost odd elements that all elements to the left is greater than it.
    748 
    749 **Hint 5**
    750 
    751 Treat the rest of elements as a new permutation
    752 
    753 **Solution**
    754 
    755 Since we need to find the lexicographically smallest permutation, our goal is to make the numbers on the left as small as possible.
    756 
    757 Suppose we have a permutation $[p_1, p_2, \ldots , p_n]$.  
    758 The first question we would like to answer is: where will the number $1$ appear in the final lexicographically smallest permutation?
    759 
    760 **Case 1: $p_1$ is odd.**
    761 
    762 In this case, the answer is straightforward — $p_1$ can always be decreased to $1$. Hence, $1$ will appear at the first position.
    763 
    764 **Case 2: $p_1$ is even.**
    765 
    766 This case is more complicated. For a number $p_i$ to be reduced to $1$, two conditions must hold:
    767 
    768 1. $p_i$ is odd.
    769 2. All numbers $1, 2, \ldots, p_i - 1$ appear to the right of index $i$.  
    770     In other words, for every $j \lt i$, we must have $p_j \gt p_i$.
    771 
    772 We find the minimum possible index $i$ that satisfies both of the above condition, and reduce $p_i$ to $1$.  
    773 After that, since $p_1$ is even, we reduce $p_1$ to $2$.
    774 
    775 It can be proven that choosing the smallest such index $i$ and performing these two reductions, first decreasing $p_i$ to $1$, then decreasing $p_1$ to $2$, will always yield the lexicographically smallest permutation. A formal proof will be given later.
    776 
    777 **Recursive construction:**
    778 
    779 * If $p_1$ is odd, reducing $p_i$ to $1$ transforms the remaining multiset $[p_2, p_3, \ldots , p_n]$ into $[2, 3, \ldots, n]$. This can be treated as a new permutation problem of size $n - 1$.
    780 * If $p_1$ is even, after reducing $p_i$ to $1$ and $p_1$ to $2$,  
    781    the remaining multiset $[p_2, p_3, \ldots, p_{i-1}, p_{i+1}, \ldots, p_n]$ becomes $[3, 4, \ldots, n]$, which again forms a smaller permutation problem of size $n - 2$.
    782 
    783 Thus, the process can be applied recursively.
    784 
    785 **Complexity Analysis:**
    786 
    787 The overall time complexity is $\mathcal{O}(n^2)$, which is efficient enough to pass the first subtask (F1).
    788 
    789 **Proof**
    790 
    791 Now let's prove that this solution always lead the permutation to smallest lexigraphically possible.
    792 
    793 Suppose we have permutation $[p_1, p_2, \ldots, p_n]$
    794 
    795 When $p_1$ is odd, the conclusion is straightforward. We can always decrease $p_1$ to $1$ and treat the remaining elements as a new permutation.
    796 
    797 When $p_1$ is even, let $i$ be the minimum possible index such that $p_i$ can be decreased to $1$. In other words, $i$ is the smallest index such that $\min(p_1, p_2, \ldots, p_{i - 1}) \gt p_i$ and $p_i$ is odd. We need to prove that decreasing $p_i$ ($1 \lt i \le n$) to $1$ does not affect the lexicographically smallest possible prefix $[p_1, p_2, \ldots, p_{i-1}]$ that can be formed.
    798 
    799 Transforming $[p_1, p_2, \ldots, p_{i-1}]$ into its lexicographically smallest possible form involves three types of operations. Suppose an operation chooses indices $x \lt y \lt z$ and performs the following steps: 1) item subtract $2$ from $p_x$, 2) add $1$ to $p_y$, and 3) add $1$ to $p_z$.
    800 
    801 We analyze each possible case relative to $i$:
    802 
    803 Case 1: $x \lt y \lt z \lt i$
    804 
    805 * This case is trivial. Changing $p_i$ to $1$ only affects indices greater than $i$, so these operations remain completely valid.
    806 
    807 Case 2: $x \lt y \lt i \lt z$
    808 
    809 * Suppose $p_z$ is within the subarray $[p_i, \ldots, p_n]$. After changing $p_i$ to $1$, the element $p_z$ (or its value) still exists, perhaps at a different position, but the multiset of values in $[p_i, \ldots, p_n]$ remains unchanged. Therefore, the operation can still be performed.
    810 
    811 Case 3: $x \lt i \lt y \lt z$
    812 
    813 * Since the operation does not depend on the relative order or values of $p_y$ and $p_z$, and the multiset $[p_i, \ldots, p_n]$ is preserved, we can still find suitable $p_y$ and $p_z$ to perform the operation. Hence, this case also remains valid.
    814 
    815 Case 4: $y = i$ or $z = i$
    816 
    817 * If $p_i \gt 1$, then after decreasing $p_i$ to $1$, there must exist some index $j \gt i$ such that $p_j$ equals the original value of $p_i$. Thus, the operation can still be performed using $p_j$.
    818 * If $p_i = 1$, then it is impossible for any $j \lt i$ to have $p_j = 1$, as that would violate the rule of minimality. This is precisely why we must choose the smallest possible index $i$ for which $p_i$ can be reduced to $1$; otherwise, the prefix could incorrectly contain $1$.
    819 
    820 Therefore, if there exists a sequence of operations that transforms $[p_1, p_2, \ldots, p_{i-1}]$ into the lexicographically smallest possible prefix, none of these operations will be affected by decreasing $p_i$ to $1$ beforehand.
    821 
    822 Hence, we can always decrease $p_i$ to $1$ without affecting the lexicographically smallest prefix.
    823 
    824 **Implementation (PyPy)**
    825 
    826 ```
    827 def main():
    828     n = int(input())
    829     p = list(map(int,input().split()))
    830     for i in range(n):
    831         p[i] -= 1
    832     seq = []
    833     indexes = [i for i in range(n)]
    834     def update(indexes):
    835         count = 0
    836         for i in range(n):
    837             if indexes[i] < 0:  continue
    838             indexes[i] = count
    839             count += 1
    840     curr = 1
    841     ans = [-1]*n
    842     for i in range(n):
    843         if ans[i] > 0:  
    844             continue
    845         if indexes[p[i]] % 2 == 0:
    846             ans[i] = curr
    847             curr += 1
    848             indexes[p[i]] = -1
    849             update(indexes)
    850             continue 
    851         prefix = p[i]
    852         pick = -1
    853         for j in range(i+1,n):
    854             if ans[j] > 0:
    855                 continue 
    856             if p[j] > prefix or indexes[p[j]] % 2 > 0:
    857                 prefix = min(prefix,p[j])
    858                 continue
    859             pick = j 
    860             break
    861         ans[j] = curr 
    862         curr += 1
    863         ans[i] = curr
    864         curr += 1
    865         indexes[p[j]] = -1
    866         indexes[p[i]] = -1
    867         update(indexes)
    868     print(*ans)      
    869 T = int(input())
    870 for _ in range(T):
    871     main()
    872 ```
    873 
    874 **Tester's Solution**
    875 
    876 **Hints**
    877 
    878 **Hint 1**
    879 
    880 Each move only shuffles the triple of **consecutive values** ${a,a+1,a+2}$ and places the **smallest** among them at the **leftmost** of the three chosen positions.
    881 
    882 **Hint 2**
    883 
    884 Think in terms of a value’s **rank** among the not-yet-fixed values: one move on a value is like moving it **two places to the left** in that order. A value at rank $r$ can move at most $\lfloor r/2\rfloor$ steps.
    885 
    886 **Hint 3**
    887 
    888 To minimize lexicographically, process positions from left to right and push the current choice as far left as allowed. Parity matters: when the current rank is odd, you must “pair” with a smaller value to make the plan realizable.
    889 
    890 **Solution**
    891 
    892 We want the lexicographically smallest permutation reachable by the triple move. Focus on the **first position** :
    893 
    894 * If the first value is **odd**, we can keep applying moves that reduce it by $2$ until it becomes **$1$**.
    895 * If it is **even**, we can keep reducing by $2$ until it becomes **$2$**.
    896 
    897 Why? Each move that subtracts $2$ from some position $i$ uses two positions $j,k$ to its right that currently hold the two consecutive values just below it. In a permutation these exist until you reach $1$ (odd start) or $2$ (even start). Using them only increases those right-side values by $1$, so they never block making the first value as small as parity allows.
    898 
    899 Now suppose the first value is even and we set it to $2$. The next question is: **where should $1$ go?** The correct choice is the **leftmost** value that can be reduced to $1$.
    900 
    901 Two simple facts characterize when a value $v$ can be reduced to a target $cnt$:
    902 
    903 1. **Parity:** moves change a value by $\pm 2$ overall, so $v \equiv cnt \pmod 2$ is necessary.
    904 2. **No smaller blockers to the left:** to reduce $v$ down step by step, for each intermediate step you must pick the pair ${x,x+1}$ with $x \in {cnt,cnt+1,\dots,v-1}$ to the **right** of $v$. So $v$ must lie to the **left** of **all** values in $[cnt, v-1]$.
    905 
    906 This gives a clean greedy: at step $cnt=1,2,\dots,n$, among values $i\in[cnt\ldots n]$, scan by increasing $i$ and keep the running **minimum position** seen so far. Every time that minimum improves (a “record minimum”), if $i \equiv cnt \pmod 2$ then value $i$ is feasible to reduce to $cnt$; among all feasible ones, the final record minimum is **leftmost** and is the one we must take.
    907 
    908 Why lexicographically optimal? The array first differs where we place $cnt$. Picking the **leftmost feasible** position ensures the smallest possible number at that index. Any alternative that puts $cnt$ strictly to the right makes the prefix strictly larger and cannot be beaten later.
    909 
    910 After choosing the index `cur` where we install $cnt$, we conceptually “pull down” the current value $val=p[cur]$ to $cnt$ by a chain of moves. Each such move also raises exactly one of the values in ${cnt,\ldots,val-1}$ by $1$. Over the whole chain, **every** number in ${cnt,\dots,val-1}$ gets raised exactly once. So, in one shot, we can **set** $p[cur]=cnt$ and **increase** all values in $[cnt \ldots val-1]$ by $1$. The remaining numbers still form a permutation of ${cnt+1,\dots,n}$, and we repeat with $cnt+1$.
    911 
    912 Because each step is just a linear scan over values and a few local updates, this runs in $\mathcal{O}(n^2)$ per test.
    913 
    914 **Implementation (C++)**
    915 
    916 ```
    917 #include <iostream>
    918 #include <vector>
    919 #include <algorithm>
    920 #include <numeric>
    921 #include <tuple>
    922 #include <map>
    923 #include <set>
    924 #include <deque>
    925 #include <queue>
    926 #include <functional>
    927 #include <cassert>
    928 #include <immintrin.h>
    929 
    930 using namespace std;
    931 
    932 #define int long long
    933 
    934 int p[100005];
    935 int pos[100005];
    936 
    937 signed main()
    938 {
    939 #if _LOCAL_
    940     freopen("case.txt", "r", stdin);
    941 #endif
    942 
    943     int t;
    944     cin >> t;
    945 
    946     while(t--) {
    947         int n;
    948         cin >> n;
    949         for(int i = 0; i < n; ++i) {
    950             cin >> p[i];
    951         }
    952         for(int i = 0; i < n; ++i) {
    953             pos[p[i]] = i;
    954         }
    955         for(int cnt = 1; cnt <= n; ++cnt) {
    956             int cur = n;
    957             for(int i = cnt, mn = n; i <= n; ++i) {
    958                 if(pos[i] < mn) {
    959                     mn = pos[i];
    960                     if((i & 1) == (cnt & 1)) {
    961                         cur = pos[i];
    962                     }
    963                 }
    964             }
    965             int val = p[cur];
    966             p[cur] = cnt;
    967             for(int i = cnt; i < val; ++i) {
    968                 p[pos[i]]++;
    969             }
    970             for(int i = val; i > cnt; --i) {
    971                 pos[i] = pos[i-1];
    972             }
    973             pos[cnt] = cur;
    974         }
    975         for(int i = 0; i < n; ++i) {
    976             cout << p[i] << ' ';
    977         }
    978         cout << endl;
    979     }
    980 
    981     return 0;
    982 }
    983 ```
    984 
    985 **MathModel's Solution (Bonus/Challenge)**
    986 
    987 **Hints**
    988 
    989 **Hint 1**
    990 
    991 A move is only possible on three consecutive values: there must exist an $m$ such that the values involved are exactly ${m,m+1,m+2}$ at indices $i\lt j\lt k$.
    992 
    993 **Hint 2**
    994 
    995 $p_i=\max(p_j,p_k)+1$ and $p_i=\min(p_j,p_k)+2$
    996 
    997 Those equations force the three values to be consecutive and the largest to sit at the leftmost index, which is exactly $c\lt \min(a,b)$ with values ${m,m+1,m+2}$.
    998 
    999 **Hint 3**
   1000 
   1001 Each move strictly decreases lexicographic order: the first changed index is $i=c$, whose value drops from $m+2$ to $m$; earlier indices remain unchanged.
   1002 
   1003 **Hint 4**
   1004 
   1005 Each move removes at least two inversions among the triple (and never adds inversions before $i$), so the process is acyclic and must terminate.
   1006 
   1007 **Hint 5**
   1008 
   1009 Number of operations is $\le \mathcal{O}(n^2)$ (each removes $\ge2$ inversions). The pointer-walk advances by $+1$ when no operations, and jumps back by at most $2$ per op. Total steps are $\mathcal{O}(n+\text{ops})=\mathcal{O}(n^2)$ overall.
   1010 
   1011 **Solution**
   1012 
   1013 **Please Read Hints**
   1014 
   1015 Maintain $pos[v]$. Iterate $m$ from $0$ to $n-3$:
   1016 
   1017 * Let
   1018 
   1019 $ a=pos[m],\quad b=pos[m+1],\quad c=pos[m+2]. $
   1020 
   1021 * If $c\lt \min(a,b)$, apply the operation on indices ${a,b,c}$:
   1022 
   1023   + Set $i=c$, $j=\min(a,b)$, $k=\max(a,b)$.
   1024   + If $a\lt b$, write $(m,m+1,m+2)$ to $(i,j,k)$ and set $(pos[m],pos[m+1],pos[m+2])=(i,j,k)$.
   1025   + Else write $(m,m+2,m+1)$ to $(i,j,k)$ and set $(pos[m],pos[m+2],pos[m+1])=(i,j,k)$.
   1026   + Then set $m\leftarrow\max(m-2,0)$.
   1027 * Otherwise, set $m\leftarrow m+1$.
   1028 
   1029 This process terminates when $m=n-2$, at which point every triple satisfies $pos[m+2]\ge\min(pos[m],pos[m+1])$, so no legal move exists anywhere. Because each step is lexicographically decreasing (when an operation is performed) and the space of permutations is finite and acyclic under these moves, the result is the lexicographically smallest reachable permutation. The pointer-walk guarantees total time $\mathcal{O}(n^2)$.
   1030 
   1031 **Challenge: Can you prove the solution?**
   1032 
   1033 **Implementation**
   1034 
   1035 ```
   1036 for _ in range(int(input())):
   1037     n=int(input())
   1038     p=list(map(int,input().split()))
   1039     pos=[0]*n
   1040     for i in range(n):
   1041         pos[p[i]-1]=i
   1042     ch=1
   1043     while ch:
   1044         ch=0
   1045         for m in range(n-2):
   1046             a,b,c=pos[m],pos[m+1],pos[m+2]
   1047             if(c<min(a,b)):
   1048                 i=c
   1049                 if(a<b):
   1050                     j,k=a,b
   1051                     p[i],p[j],p[k]=m+1,m+2,m+3
   1052                     pos[m],pos[m+1],pos[m+2]=i,j,k
   1053                 else:
   1054                     j,k=b,a
   1055                     p[i],p[j],p[k]=m+1,m+3,m+2
   1056                     pos[m],pos[m+2],pos[m+1]=i,j,k
   1057                 ch=1
   1058     print(*p)
   1059 ```
   1060 
   1061 **Rate The Problem !**
   1062 
   1063 Great
   1064 
   1065 Good
   1066 
   1067 Neutral
   1068 
   1069 Bad
   1070 
   1071 Didn't Solve
   1072 
   1073 #### [2156F2 - Strange Operation (Hard Version)](/contest/2156/problem/F2 "Codeforces Round 1061 (Div. 2)")
   1074 
   1075 **Hints**
   1076 
   1077 **Hint 1**
   1078 
   1079 Suppose the operation changes indices $i, j, k$, other than $i$, all the other indices relative position doesn't change.
   1080 
   1081 **Hint 2**
   1082 
   1083 Use segment tree and fenwick tree
   1084 
   1085 **Hint 3**
   1086 
   1087 Iterate from $1$ to $n$, during the $t$-th iteration, find the leftmost element that can be decreased by $t$.
   1088 
   1089 **Hint 4**
   1090 
   1091 Acclerate the procedure by finding next smaller element.
   1092 
   1093 **Solution**
   1094 
   1095 **You should Read Editorial of F1 First**
   1096 
   1097 Let the initial permutation be $p=(p_1,p_2,\dots,p_n)$, and let the final array be $q=(q_1,q_2,\dots,q_n)$. Initialize $q_i=0$ for all $i$, meaning every position in the output is still undetermined. During the $t$-th iteration, find the smallest index $i$ whose value can be decreased to $t$. Repeatedly choose this $i$, locate indices $j,k$ such that $p_i=\max(p_j,p_k)+1$ and $p_i=\min(p_j,p_k)+2$, and perform the updates $p_i\leftarrow p_i-2$, $p_j\leftarrow p_j+1$, $p_k\leftarrow p_k+1$. This is equivalent to removing $p_i$ and setting $q_i\gets t$. After removing $p_i$, the remaining elements $p_1,\dots,p_{i-1},p_{i+1},\dots,p_n$ close the gap (preserving relative order), forming a permutation of length $n-1$.
   1098 
   1099 This remove-and-assign simulation can be supported by a Fenwick tree or a segment tree so that each update and query runs in $\mathcal{O}(\log n)$ time; however, naively finding the correct index $i$ could still cost $\mathcal{O}(n)$ per step. Define the rank of $p_i$ as the number of alive (not yet removed) elements that are not greater than $p_i$, including $p_i$ itself.
   1100 
   1101 To speed up the process, keep a pointer at the smallest alive index $i$ and check its rank. If the rank is odd, remove this element immediately. If the rank is even, move the pointer to the next smaller element to its right, that is, to the smallest $ j \gt i$ with $p_j \lt p_i$. Continue until you reach an element with odd rank.
   1102 
   1103 Although a single "move to the next smaller on the right" step may look linear, the total number of such moves over the whole algorithm is at most $2n$. If an element is first visited when its rank is even, after some element to its right is removed, its rank becomes odd the next time it is visited; if an element’s rank is already odd, it is removed immediately upon visit. Therefore each index is visited at most twice.
   1104 
   1105 To implement this, we maintain two data structures:
   1106 
   1107 1. A Fenwick tree over values, where a $1$ at position $p_i$ indicates that the value $p_i$ is still alive (and $0$ otherwise). This lets you query the current rank of $p_i$ in $\mathcal{O}(\log n)$ time.
   1108 2. Let $ip$ denote the array that is the inverse of $p$, i.e., $ip_{p_i} = i$. Store a range-min segment tree over the array $ip$ . When the value $p_i$ is removed, set $ip_{p_i}=\infty$. If the current visited index is $i$, then a range-min query on $[1,p_i-1]$ returns the minimum position $j$ such that $j \gt i$ and $p_j \lt p_i$ (the next smaller element on the right by value). Each query and update costs $\mathcal{O}(\log n)$, and each index is examined at most twice, so the overall complexity is $\mathcal{O}(n\log n)$, which is sufficient for the F2 constraints.
   1109 
   1110 **Implementation (hxu10,PyPy)**
   1111 
   1112 ```
   1113 inf = 10**9
   1114 
   1115 class fenwick(object):
   1116     def __init__(self, n):
   1117         self.n = n
   1118         self.cul = [0]*n
   1119         self.maxd = len(bin(n))-3
   1120     def update(self,index,diff):
   1121         i = index
   1122         while i<self.n:
   1123             self.cul[i] += diff
   1124             i += (i+1)&(-i-1)
   1125     def getaccu(self,index):
   1126         output = 0
   1127         i = index
   1128         while i>=0:
   1129             output += self.cul[i]
   1130             i -= (i+1)&(-i-1)
   1131         return output
   1132 
   1133 class segment_tree(object):
   1134     def merge(self,num,accu):
   1135         return min(accu,num)
   1136     def __init__(self,n,initial):
   1137         self.n = n
   1138         self.inf = inf
   1139         self.arr = [self.inf]*(2*n)
   1140         for i in range(2*n-1,0,-1):
   1141             if i>=n:  self.arr[i] = initial[i-n]
   1142             else:     self.arr[i] = self.merge(self.arr[2*i],self.arr[2*i+1])
   1143 
   1144     def update(self,index,target):
   1145         index += self.n
   1146         self.arr[index] = target
   1147         while index > 0:
   1148             if index & 1:
   1149                 nexttarget = self.merge( self.arr[index], self.arr[index-1])
   1150             else:
   1151                 nexttarget = self.merge( self.arr[index], self.arr[index+1])
   1152             self.arr[index>>1] = nexttarget
   1153             index = index >> 1
   1154 
   1155     def addnum(self,index,diff):
   1156         self.update(index, self.arr[index+self.n] + diff)
   1157 
   1158     def query(self,left,right):
   1159         i,j = self.n+left,  self.n+right+1
   1160         output = self.inf  # initial output should be changed if you want to change the merge function
   1161         while i<j:
   1162             if i&1:
   1163                 output = self.merge(self.arr[i],output)
   1164                 i += 1
   1165             if j&1:
   1166                 j -= 1
   1167                 output = self.merge(self.arr[j],output)
   1168             i = i >> 1
   1169             j = j >> 1
   1170         return output
   1171 
   1172 def main(t):
   1173     n = int(input())
   1174     p = list(map(int,input().split()))
   1175     location = [0]*n
   1176     for i in range(n):
   1177         p[i] -= 1
   1178         location[p[i]] = i 
   1179     seg = segment_tree(n, location)
   1180     fen = fenwick(n)
   1181     for i in range(n):
   1182         fen.update(i,1)
   1183     ans = [-1]*n
   1184     curr = 1
   1185     for i in range(n):
   1186         if ans[i] >= 0:  
   1187             continue 
   1188         index = fen.getaccu(p[i]) - 1
   1189         if index % 2 == 0:
   1190             fen.update(p[i],-1)
   1191             seg.update(p[i],inf)
   1192             ans[i] = curr 
   1193             curr += 1
   1194             continue
   1195         j = i 
   1196         while True:
   1197             j = seg.query(0,p[j]-1) 
   1198             nextindex = fen.getaccu(p[j]) - 1
   1199             if nextindex % 2 > 0:
   1200                 continue 
   1201             break
   1202         ans[j] = curr 
   1203         ans[i] = curr + 1
   1204         curr += 2
   1205         seg.update(p[i],inf)
   1206         seg.update(p[j],inf)
   1207         fen.update(p[i],-1)
   1208         fen.update(p[j],-1)
   1209     print(*ans)
   1210 
   1211 T = int(input())
   1212 for t in range(T):
   1213     main(t)
   1214 ```
   1215 
   1216 **Rate The Problem !**
   1217 
   1218 Great
   1219 
   1220 Good
   1221 
   1222 Neutral
   1223 
   1224 Bad
   1225 
   1226 Didn't Solve