codeforces-scrape

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

2154.md (44652B)


      1 Source: https://codeforces.com/blog/entry/147471
      2 
      3 Thank you for participating!
      4 
      5 Special thanks to [reirugan](/profile/reirugan "Master reirugan") for writing the analysis for **B, D, E** and to [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") and [Friedrich](/profile/Friedrich "Master Friedrich") for helping to optimise **F1**, leading to the creation of **F2**.
      6 
      7 **Rating Predictions**
      8 
      9 | Problem | A | B | C1 | C2 | D | E | F1 | F2 |
     10 | --- | --- | --- | --- | --- | --- | --- | --- | --- |
     11 | [reirugan](/profile/reirugan "Master reirugan") | 800 | 1100 | 1200 | 1600 | 1700 | 2000 | 2200 | ¯\_(ツ)_/¯ |
     12 | [eric899](/profile/eric899 "Pupil eric899") | 800 | 1000 | 1300 | ¯\_(ツ)_/¯ | 1600 | ¯\_(ツ)_/¯ | ¯\_(ツ)_/¯ | ¯\_(ツ)_/¯ |
     13 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 1100 | 1500 | 1900 | 1600 | 2100 | 2300 | 2600 |
     14 | [_istil](/profile/_istil "Grandmaster _istil") | 800 | 1100 | 1400 | 1800 | 1800 | 2100 | 2000 | 2500 |
     15 | [anango](/profile/anango "International Master anango") | 800 | 1100 | 1300 | 1900 | 1800 | 2200 | 2400 | 2700 |
     16 | [FetFot](/profile/FetFot "Master FetFot") | 800 | 1100 | 1400 | 1800 | 1900 | ¯\_(ツ)_/¯ | 2400 | ¯\_(ツ)_/¯ |
     17 | [Intellegent](/profile/Intellegent "International Master Intellegent") | 800 | 1000 | 1300 | 1900 | 1800 | 2300 | 2200 | 2800 |
     18 | [nifeshe](/profile/nifeshe "Grandmaster nifeshe") | 800 | 1000 | 1200 | 1800 | 1800 | 2400 | 2500 | 2800 |
     19 | [satyam343](/profile/satyam343 "Candidate Master satyam343") | 800 | 1000 | 1400 | 1900 | 1800 | 2400 | 2500 | 2700 |
     20 | [catgirl](/profile/catgirl "Master catgirl") | 800 | 1000 | 1300 | 1700 | 1500 | 2200 | 2200 | 2700 |
     21 | [wuhudsm](/profile/wuhudsm "Master wuhudsm") | 800 | 1100 | 1400 | 2000 | 1600 | 2200 | ¯\_(ツ)_/¯ | ¯\_(ツ)_/¯ |
     22 | [Edeeva](/profile/Edeeva "Candidate Master Edeeva") | 800 | 900 | 1100 | 1800 | 1700 | 2300 | ¯\_(ツ)_/¯ | ¯\_(ツ)_/¯ |
     23 | Actual rating | 800 | 1000 | 1400 | 2000 | 1900 | 2500 | 2700 | 3300 |
     24 
     25 [2154A - Notelock](/contest/2154/problem/A "Codeforces Round 1060 (Div. 2)"):
     26 
     27 **Hint 1**
     28 
     29 If there is a subarray containing $k - 1$ zeros, then the next element cannot be prevented from being hit. So any time we see $k - 1$ zeros follwed by a one then the one must be protected.
     30 
     31 **Solution**
     32 
     33 From Hint 1, lets protect every $\mathtt{1}$ that fits the pattern. Furthermore we should always protect the first $1$ in the string so lets do that. It turns out that this is all that we need to do, to prove this think inductively: every element that is not protected will always have a $\mathtt{1}$ in the last $k - 1$ elements and so it will be unchanged. So to solve the problem we can check the distance between each consecutive $\mathtt{1}$, if the gap is at least $k$ then add $1$ to the answer. Final time complexity $O(n)$.
     34 
     35 **Implementation(C++)**
     36 
     37 ```
     38 #include<bits/stdc++.h>
     39 using namespace std;
     40 typedef long long ll;
     41 #define debug(x) cout << #x << " = " << x << "\n";
     42 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
     43 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
     44 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
     45 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
     46 
     47 void solve(){
     48     int n, k;
     49     cin >> n >> k;
     50 
     51     string s;
     52     cin >> s;
     53 
     54     int ans = 0;
     55     int last = -1e9;
     56     for (int i = 0; i < n; i++){
     57         if (s[i] == '1' && i - last >= k)
     58             ans++;
     59         if (s[i] == '1')
     60             last = i;
     61     }
     62 
     63     cout << ans << "\n";
     64 }
     65 
     66 int main(){
     67     ios::sync_with_stdio(false);
     68     cin.tie(0);
     69     
     70     int t;
     71     cin >> t;
     72     while (t--) solve();
     73 }
     74 ```
     75 
     76 **Implementation(Minecraft)**
     77 
     78 <https://youtu.be/5Xku9F6Rbqo>
     79 
     80 [2154B - Make it Zigzag](/contest/2154/problem/B "Codeforces Round 1060 (Div. 2)"):
     81 
     82 **Hint 1**
     83 
     84 You want odd-indexed values to be small, and even-indexed values to be large. In other words, it is beneficial to apply operation 1 on even indices, and operation 2 on odd indices.
     85 
     86 **Hint 2**
     87 
     88 Since operation 1 is free, you may as well apply it to every even index. None of the operations can increase a prefix max, so you can't possibly do any better than just applying operation 1 immediately to every even index.
     89 
     90 **Solution**
     91 
     92 Let's first apply operation 1 to every even index. Now, we can't further increase any even-indexed values, so we just need to decrease odd-indexed values by using operation 2. All of the odd indices are independent from one another, so let's just consider each one separately. For a fixed odd index $i$, the number of instances of operation 2 needed to make it smaller than $a_{i-1}$ and $a_{i+1}$ is given by $\max(0, a_i - \min(a_{i-1}, a_{i+1}) + 1)$. (Be careful with indices $1$ and $n$ as well; you can treat the out of bounds values as being arbitrarily large, or just take care of them separately.) Now, we sum this value, across all odd indices $i$.
     93 
     94 **Implementation(C++)**
     95 
     96 ```
     97 #include<bits/stdc++.h>
     98 using namespace std;
     99 typedef long long ll;
    100 #define debug(x) cout << #x << " = " << x << "\n";
    101 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    102 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    103 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    104 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    105 
    106 void solve(){
    107     int n;
    108     cin >> n;
    109 
    110     vector<int> a(n);
    111     for (int &x : a) cin >> x;
    112 
    113     vector<int> pre(n);
    114     pre[0] = a[0];
    115     for (int i = 1; i < n; i++)
    116         pre[i] = max(pre[i - 1], a[i]);
    117 
    118     ll ans = 0;
    119     for (int i = 0; i < n; i += 2){
    120         int dif = -1;
    121         if (i > 0)
    122             dif = max(dif, a[i] - pre[i - 1]);
    123 
    124         if (i < n - 1)
    125             dif = max(dif, a[i] - pre[i + 1]);
    126 
    127         ans += dif + 1;
    128     }
    129 
    130     cout << ans << "\n";
    131 }
    132 
    133 int main(){
    134     ios::sync_with_stdio(false);
    135     cin.tie(0);
    136     
    137     int t;
    138     cin >> t;
    139     while (t--) solve();
    140 }
    141 ```
    142 
    143 [2154C1 - No Cost Too Great (Easy Version)](/contest/2154/problem/C1 "Codeforces Round 1060 (Div. 2)"):
    144 
    145 **Hint 1**
    146 
    147 You can make an element divisible by $2$ in $1$ move.
    148 
    149 **Hint 2**
    150 
    151 Can you check if the answer is $0$ or if the answer is $1$?
    152 
    153 **Solution**
    154 
    155 By result of Hint 1, the answer cannot be more than $2$, as we can always pick two elements and make them both divisible by $2$ using at most $1$ move on each. So now we just need to check if the answer is $0$ or $1$.
    156 
    157 To check if the answer is $0$, we need to determine if there is a common divisor between two elements. Note that it is sufficient to only check if there is a common prime divisor. So, for each element, iterate through all its prime divisors and check if there is another element with the same prime divisor.
    158 
    159 To check if the answer is $1$, we can do the same as $0$. This time, for each $i$ we check if $a_i + 1$ shares a common prime divisor with another element.
    160 
    161 Prime divisors can be pre-calculated with the Sieve of Eratosthenes in $O(N\log\log N)$ where $N$ is the maximum possible element (so $2 \cdot 10^5$ for this problem). However, the constraints are lenient enough to allow $O(n\sqrt{N})$ as well.
    162 
    163 The final complexity comes out to $O(n\omega(N) + N\log\log N)$, where $\omega(x)$ is used to denote the number of distinct prime divisors of $x$. Note that the editorial implementation is $O(n\omega(N)\log(n\omega(N)) + N\log\log N)$ due to use of c++ std::map for the sake of readability.
    164 
    165 **Implementation(C++)**
    166 
    167 ```
    168 #include<bits/stdc++.h>
    169 using namespace std;
    170 typedef long long ll;
    171 #define debug(x) cout << #x << " = " << x << "\n";
    172 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    173 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    174 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    175 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    176 
    177 const int N = 2e5 + 10;
    178 vector<vector<int>> pfac(N + 1);
    179 
    180 void solve(){
    181     int n;
    182     cin >> n;
    183 
    184     vector<int> a(n), b(n);
    185     for (int &x : a) cin >> x;
    186     for (int &x : b) cin >> x;
    187 
    188     int ans = 2;
    189     map<int, int> cnt;
    190     for (int i = 0; i < n; i++){
    191         for (int x : pfac[a[i]]){
    192             if (cnt[x] > 0)
    193                 ans = 0;
    194             cnt[x]++;
    195         }
    196     }
    197 
    198     for (int i = 0; i < n; i++){
    199         for (int x : pfac[a[i]])
    200             cnt[x]--;
    201 
    202         for (int x : pfac[a[i] + 1]){
    203             if (cnt[x] > 0)
    204                 ans= min(ans, 1);
    205         }
    206 
    207         for (int x : pfac[a[i]])
    208             cnt[x]++;
    209     }
    210 
    211     cout << ans << "\n";
    212 }
    213 
    214 int main(){
    215     ios::sync_with_stdio(false);
    216     cin.tie(0);
    217 
    218     for (int i = 2; i <= N; i++){
    219         if (!pfac[i].empty())
    220             continue;
    221 
    222         for (int j = i; j <= N; j += i)
    223             pfac[j].push_back(i);
    224     }
    225     
    226     int t;
    227     cin >> t;
    228     while (t--) solve();
    229 }
    230 ```
    231 
    232 [2154C2 - No Cost Too Great (Hard Version)](/contest/2154/problem/C2 "Codeforces Round 1060 (Div. 2)"):
    233 
    234 **Hint 1**
    235 
    236 Solve the easy version.
    237 
    238 **Hint 2**
    239 
    240 We can always make two elements $i, j$ divisible by $2$ with no more than $b_i + b_j$ cost.
    241 
    242 **Hint 3**
    243 
    244 By hint 2, we should never perform more than one operation on more than one element.
    245 
    246 **Solution**
    247 
    248 Lets say we are trying to make the elements at index $i, j$ have a common divisor. From hint 2 and 3 there are only two cases to consider here. The first case where we make $0$ or $1$ operation on both $i$ and $j$. Or the second case where we make more than $1$ operation on a single element. We should never do more than $1$ operation on both elements because we can always do better by making both elements divisible by $2$.
    249 
    250 So now to solve the problem on the entire array, we should try to solve both of the cases. For convenience lets reorder the elements so that $b$ is in sorted order.
    251 
    252 The first case can be solve almost identically to the easy version of the problem. We can always do at least as good as $b_1 + b_2$, the only other possibility is only making one operation. To do this we just check if $a_i + 1$ has a common prime divisor with another element.
    253 
    254 The second case is the more tricky case, we need to check the optimal way to make more than one operations for each element, and it is probably the crux of the problem. The key thing to notice is that we actually do not need to check every element, in fact we can only check the element with the smallest value of $b_i$ ($b_1$ because $b$ is sorted). To prove this lets argue by contradiction, supposed we made $k$ ($k \ge 2$) operations on element $x$ ($x \ge 2$). The total cost of this is $k \cdot b_x$, we know from hint 2 that we can do $b_1 + b_x$ or better, since $b_1$ is the smallest element we know that $b_1 + b_x \le k \cdot b_x$ and thus we do not need to consider this case!
    255 
    256 So now we need to quickly check what is the optimal way to use multiple operations on the first element. To do this we can iterate through all the prime divisors of the other elements and determine the minimum number of operations to make $a_1$ divisible by it.
    257 
    258 The final time complexity comes out to $O(n\omega(N) + N\log\log N)$, where $\omega(x)$ is used to denote the number of distinct prime divisors of $x$. Note that the editorial implementation is $O(n\omega(N)\log(n\omega(N)) + N\log\log N)$ due to use of c++ std::map for the sake of readability.
    259 
    260 **Implementation(C++)**
    261 
    262 ```
    263 #include<bits/stdc++.h>
    264 using namespace std;
    265 typedef long long ll;
    266 #define debug(x) cout << #x << " = " << x << "\n";
    267 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    268 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    269 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    270 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    271 
    272 const int N = 2e5 + 10;
    273 vector<vector<int>> pfac(N + 1);
    274 
    275 void solve(){
    276     int n;
    277     cin >> n;
    278 
    279     vector<int> a(n), b(n);
    280     for (int &x : a) cin >> x;
    281     for (int &x : b) cin >> x;
    282 
    283     vector<int> ord(n);
    284     iota(ord.begin(), ord.end(), 0);
    285     sort(ord.begin(), ord.end(), [&](int x, int y) -> bool{
    286         return b[x] < b[y];
    287     });
    288 
    289     int ans = b[ord[0]] + b[ord[1]];
    290     map<int, int> cnt;
    291     for (int i = 0; i < n; i++){
    292         for (int x : pfac[a[i]]){
    293             if (cnt[x] > 0)
    294                 ans = 0;
    295             cnt[x]++;
    296         }
    297     }
    298 
    299     for (int i = 0; i < n; i++){
    300         for (int x : pfac[a[i]])
    301             cnt[x]--;
    302 
    303         for (int x : pfac[a[i] + 1]){
    304             if (cnt[x] > 0)
    305                 ans= min(ans, b[i]);
    306         }
    307 
    308         for (int x : pfac[a[i]])
    309             cnt[x]++;
    310     }
    311 
    312     int idx = ord[0];
    313     vector<int> check;
    314     for (int i = 0; i < n; i++){
    315         if (i == idx)
    316             continue;
    317 
    318         for (int x : pfac[a[i]])
    319             check.push_back(x);
    320     }
    321 
    322     for (int x : check){
    323         int times = x - (a[idx] % x);
    324         if (times == x)
    325             times = 0;
    326 
    327         ans = min(1LL * ans, 1LL * times * b[idx]);
    328     }
    329 
    330     cout << ans << "\n";
    331 }
    332 
    333 int main(){
    334     ios::sync_with_stdio(false);
    335     cin.tie(0);
    336 
    337     for (int i = 2; i <= N; i++){
    338         if (!pfac[i].empty())
    339             continue;
    340 
    341         for (int j = i; j <= N; j += i)
    342             pfac[j].push_back(i);
    343     }
    344     
    345     int t;
    346     cin >> t;
    347     while (t--) solve();
    348 }
    349 ```
    350 
    351 [2154D - Catshock](/contest/2154/problem/D "Codeforces Round 1060 (Div. 2)"):
    352 
    353 **Hint 1**
    354 
    355 Destroying a leaf will never split the tree.
    356 
    357 **Hint 2**
    358 
    359 Trees are bipartite. In particular, you can root the tree arbitrarily, then partition vertices into those with even depth and those with odd depth. All edges connect an even depth vertex to an odd depth vertex.
    360 
    361 **Solution**
    362 
    363 We would like to decrease the size of the tree by one vertex using no more than three moves. To do so, we will pick an arbitrary leaf $v$ and destroy it. However, we must make sure that we do not destroy the vertex we are standing on, and that we do not have two consecutive instances of the second instruction. To do so, let's root the tree arbitrarily, and color vertices with even depth red and vertices with odd depth blue. We maintain the color of the vertex we are standing on, noting that every instance of instruction 1 flips the color. Now, if we are standing on the same color as $v$, we apply operation 1 once. Otherwise, we apply operation 1 twice. Thus, we are not currently standing on leaf $v$, so now we can destroy $v$. Since we applied at least one instance of instruction 1, we do not have two consecutive instances of instruction 2. By iterating this process until the only remaining vertex is vertex $n$, we guarantee that we have reached vertex $n$.
    364 
    365 **Implementation(C++)**
    366 
    367 ```
    368 #include<bits/stdc++.h>
    369 using namespace std;
    370 typedef long long ll;
    371 #define debug(x) cout << #x << " = " << x << "\n";
    372 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    373 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    374 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    375 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    376 
    377 void solve(){
    378     int n;
    379     cin >> n;
    380 
    381     vector<vector<int>> g(n);
    382     for (int i = 0; i < n - 1; i++){
    383         int u, v;
    384         cin >> u >> v;
    385         u--;
    386         v--;
    387 
    388         g[u].push_back(v);
    389         g[v].push_back(u);
    390     }
    391 
    392     vector<int> dep(n), par(n), ch(n);
    393     auto dfs = [&](auto self, int c, int p) -> void{
    394         if (p != -1)
    395             dep[c] = dep[p] + 1;
    396         par[c] = p;
    397         
    398         for (int x : g[c]){
    399             if (x == p) continue;
    400             
    401             self(self, x, c);
    402             ch[c]++;
    403         }
    404     };
    405     dfs(dfs, n - 1, -1);
    406 
    407     array<vector<int>, 2> leaves;
    408     leaves[0];
    409 
    410     for (int i = 0; i < n; i++){
    411         if (ch[i] == 0)
    412             leaves[dep[i] & 1].push_back(i);
    413     }
    414 
    415     vector<array<int, 2>> ans;
    416     int col = dep[0] & 1;
    417     for (int i = 0; i < n - 1; i++){
    418         if (leaves[col ^ 1].empty()){
    419             ans.push_back({1, -1});
    420             col ^= 1;
    421         }
    422 
    423         int nxt = leaves[col ^ 1].back();
    424         leaves[col ^ 1].pop_back();
    425         ans.push_back({2, nxt});
    426 
    427         int p = par[nxt];
    428         ch[p]--;
    429         if (ch[p] == 0)
    430             leaves[dep[p] & 1].push_back(p);
    431 
    432         ans.push_back({1, -1});
    433         col ^= 1;
    434     }
    435 
    436     cout << ans.size() << "\n";
    437     for (auto [x, y] : ans){
    438         if (x == 1)
    439             cout << "1\n";
    440         else
    441             cout << "2 " << y + 1 << "\n";
    442     }
    443 }
    444 
    445 int main(){
    446     ios::sync_with_stdio(false);
    447     cin.tie(0);
    448     
    449     int t;
    450     cin >> t;
    451     while (t--) solve();
    452 }
    453 ```
    454 
    455 **Bonus**
    456 
    457 Can you implement the checker?
    458 
    459 [2154E - No Mind To Think](/contest/2154/problem/E "Codeforces Round 1060 (Div. 2)"):
    460 
    461 **Hint 1**
    462 
    463 Without loss of generality, assume the array is sorted. Let's fix $x = 2y+1$, and let's also fix the median of a given operation $a_i$, for some $y+1 \leq i\leq n-y$. Now, we see that the best subsequence to choose is $a_1, a_2, \dots, a_y, a_i, a_{i+1}, \dots, a_{i+y}$, because we must choose $y$ values to the left of $a_i$ and $y$ values to the right of $a_i$, and we would like to change the smallest values possible.
    464 
    465 **Hint 2**
    466 
    467 Suppose you have applied one operation with median $a_i$ and another operation with median $a_j$, for $y+1 \leq i \lt j \leq n-y$. Now, you have increased up to $\min(2y, j-1)$ of the smallest values to either $a_i$ or $a_j$, since you can increase up to $y$ values smaller than the median each operation. However, you have also decreased $y$ values after $a_i$, and $y$ values after $a_j$. Instead, you might as well have just applied two operations with median $a_j$, which allows you to increase $\min(2y, j-1)$ of the smallest values to $a_j$, and decrease only the $y$ values after $a_j$. Therefore, there exists some optimal sequence of operations where we use the same median across all operations.
    468 
    469 **Solution**
    470 
    471 By the result of Hint 2, there exists some optimal sequence of operations where we use the same median across all operations. Let's fix the median at $a_i$. Now, if we choose $x = 2y+1$ for some $0\leq y \leq \min(i-1, n-i)$, we are able to increase the values of $a_1, a_2, \dots, a_{\min(ky, i-1)}$ to $a_i$, but we must also decrease the values of $a_{i+1}, a_{i+2}, \dots, a_{i+y}$ to $a_i$.
    472 
    473 The benefits of increasing $y$ are that we can increase more values, but notice that these benefits are getting less and less, because we are increasing values that are already larger. For example, the benefit of increasing $y$ from $0$ to $1$ is that now we can increase the values $a_1, a_2, \dots, a_k$, but the benefit from increasing $y$ from $1$ to $2$ is that now we can increase the values $a_{k+1}, a_{k+2}, \dots, a_{2k}$; increasing $y$ from $1$ to $2$ is not as beneficial as increasing $y$ from $0$ to $1$, because the values we are increasing are already relatively big. (There's a small case to think about, when $ky$ first exceeds $i-1$, but note that the number of values you can increase is also monotonically decreasing, so this doesn't cause any issues.) The same reasoning goes for the losses. The losses of increasing $y$ are that we are forced to decrease more values, and these losses are getting greater and greater. If we increase $y$ from $0$ to $1$, we are only forced to decrease $a_{i+1}$, but if we increase $y$ from $1$ to $2$, we now have to decrease $a_{i+2}$, which is worse because $a_{i+2}$ is relatively big. In other words, our net gains (that is, the benefits minus the losses) are monotonically decreasing.
    474 
    475 We want to keep incrementing $y$ as long as our net gains are positive, then stop incrementing $y$ once our net gains become negative. Since our net gains are monotonically decreasing, we can binary search for this point. (Alternative solutions might use ternary search instead.) So we iterate over all choices of $i$, then binary search for the optimal choice of $y$, which in total takes $O(n\log{n})$ time. Note that all computations can be done quickly with prefix sums.
    476 
    477 **Implementation(C++)**
    478 
    479 ```
    480 #include<bits/stdc++.h>
    481 using namespace std;
    482 typedef long long ll;
    483 #define debug(x) cout << #x << " = " << x << "\n";
    484 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    485 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    486 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    487 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    488 
    489 void solve(){
    490     int n, k;
    491     cin >> n >> k;
    492 
    493     vector<int> a(n);
    494     for (int &x : a) cin >> x;
    495 
    496     sort(a.begin(), a.end());
    497 
    498     vector<ll> pre(n);
    499     pre[0] = a[0];
    500     for (int i = 1; i < n; i++)
    501         pre[i] = pre[i - 1] + a[i];
    502 
    503     ll ans = pre[n - 1];
    504 
    505     auto query = [&](int l, int r) -> ll{
    506         ll res = pre[r];
    507         if (l > 0)
    508             res -= pre[l - 1];
    509         return res;
    510     };
    511 
    512     for (int i = 0; i < n; i++){
    513         int l = 1, r = min(i, n - i - 1) + 1;
    514         while (l < r){
    515             int mid = (l + r) / 2;
    516             
    517             int left = min(1LL * (mid - 1) * k, 1LL * i);
    518             int right = min(1LL * mid * k - 1, 1LL * i);
    519             ll cost = query(left, right) + a[i + mid];
    520             if (cost <= 1LL * a[i] * (right - left + 1 + 1))
    521                 l = mid + 1;
    522             else
    523                 r = mid;
    524         }
    525         l--;
    526         if (l == 0)
    527             continue;
    528 
    529         int right = min(1LL * l * k - 1, 1LL * i);
    530         ll len = right + 1 + l;
    531         ll cost = len * a[i] - (query(0, right) + query(i + 1, i + l));
    532         ans = max(ans, pre[n - 1] + cost);
    533     }
    534 
    535     cout << ans << "\n";
    536 }
    537 
    538 int main(){
    539     ios::sync_with_stdio(false);
    540     cin.tie(0);
    541     
    542     int t;
    543     cin >> t;
    544     while (t--) solve();
    545 }
    546 ```
    547 
    548 [2154F1 - Bombing (Easy Version)](/contest/2154/problem/F1 "Codeforces Round 1060 (Div. 2)"):
    549 
    550 **Hint 1**
    551 
    552 For every valid permutation we can always determine the index $k$ used as the split in the riffle shuffle operation, unless it is the sorted permutation.
    553 
    554 **Hint 2**
    555 
    556 Find the number of riffle shuffles for each split.
    557 
    558 **Solution**
    559 
    560 Lets prove Hint 1. For a valid permutation $q$, consider the first $k$ such that $k$ appers after $k + 1$ in $q$, if $q$ is a riffle shuffle of $[1, 2, \ldots, n]$ then we know that $k$ must be the split used. The only permutation where such a item does not exist is the one where the permutation is already sorted.
    561 
    562 Now lets try finding the number of solutions for a specific split point $k$ in sub-quadratic time. We can think of it like this, colour all the numbers less than or equal to $k$ in blue and the elements bigger than $k$ in red. Now when we replace all $-1$ in $p$ the following must be true after, for each blue element $x$ exactly $x$ elements are blue in its prefix and for each red element $x$ exactly $x - k$ elements are red in its prefix. So now we just need to count the number of ways to insert red and blue elements so that this condition is satisfied. To find this iterate over each index that is not $-1$ and insert the number of elements of its colour that it demands and fill the remaining elements in its prefix with the other colour. This will have worst case $O(n)$ run time if we can calculate the required binomial coefficients in $O(1)$ which can be done by pre-calculating factorials.
    563 
    564 So we can just iterate over each split and sum in $O(n^2)$ making sure to remember that we might overcount the sorted permutation.
    565 
    566 **Implementation(C++)**
    567 
    568 ```
    569 #include<bits/stdc++.h>
    570 using namespace std;
    571 typedef long long ll;
    572 #define debug(x) cout << #x << " = " << x << "\n";
    573 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    574 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    575 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    576 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    577 
    578 const int MOD = 998244353;
    579 
    580 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged
    581 struct modnum {
    582     static constexpr bool is_big_mod = mod > numeric_limits<int>::max();
    583 
    584     using S = conditional_t<is_big_mod, ll, int>;
    585     using L = conditional_t<is_big_mod, __int128, ll>;
    586 
    587     S x;
    588 
    589     modnum() : x(0) {}
    590     modnum(ll _x) {
    591         _x %= static_cast<ll>(mod);
    592         if (_x < 0) { _x += mod; }
    593         x = _x;
    594     }
    595 
    596     modnum pow(ll n) const {
    597         modnum res = 1;
    598         modnum cur = *this;
    599         while (n > 0) {
    600             if (n & 1) res *= cur;
    601             cur *= cur;
    602             n /= 2;
    603         }
    604         return res;
    605     }
    606     modnum inv() const { return (*this).pow(mod-2); }
    607     
    608     modnum& operator+=(const modnum& a){
    609         x += a.x;
    610         if (x >= mod) x -= mod;
    611         return *this;
    612     }
    613     modnum& operator-=(const modnum& a){
    614         if (x < a.x) x += mod;
    615         x -= a.x;
    616         return *this;
    617     }
    618     modnum& operator*=(const modnum& a){
    619         x = static_cast<L>(x) * a.x % mod;
    620         return *this;
    621     }
    622     modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    623     
    624     friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    625     friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    626     friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    627     friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    628     
    629     friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    630     friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    631     friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }
    632 
    633     friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    634     friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
    635 };
    636 
    637 using mint = modnum<MOD>;
    638 
    639 struct Combi{
    640     vector<mint> _fac, _ifac;
    641     int n;
    642     
    643     Combi() {
    644         n = 1;
    645         _fac.assign(n + 1, 1);
    646         _ifac.assign(n + 1, 1);
    647     }
    648     
    649     void check_size(int m){
    650         int need = n;
    651         while (need < m) need *= 2;
    652         m = need;
    653         if (m <= n) return;
    654         
    655         _fac.resize(m + 1);
    656         _ifac.resize(m + 1);
    657         for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1];
    658         
    659         _ifac[m] = _fac[m].inv();
    660         for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
    661         n = m;
    662     }
    663     
    664     mint fac(int m){
    665         check_size(m);
    666         return _fac[m];
    667     }
    668     
    669     mint ifac(int m){
    670         check_size(m);
    671         return _ifac[m];
    672     }
    673     
    674     mint ncr(int n, int r){
    675         if (n < r || r < 0) return 0;
    676         
    677         return fac(n) * ifac(n - r) * ifac(r);
    678     }
    679     
    680     mint npr(int n, int r){
    681         if (n < r || r < 0) return 0;
    682         
    683         return fac(n) * ifac(n - r);
    684     }
    685 } comb;
    686 
    687 void solve(){
    688     int n;
    689     cin >> n;
    690 
    691     vector<int> a(n);
    692     for (int &x : a) {
    693         cin >> x;
    694         if (x != -1)
    695             x--;
    696     }
    697 
    698     mint ans = 0;
    699 
    700     for (int i = 0; i < n - 1; i++){
    701         mint res = 1;
    702         int spaces = 0;
    703         int less = -1;
    704         int more = i;
    705         for (int j = 0; j < n; j++){
    706             if (a[j] == -1){
    707                 spaces++;
    708                 continue;
    709             }
    710 
    711             if (a[j] <= i){
    712                 int need = a[j] - less - 1;
    713                 res *= comb.ncr(spaces, need);
    714                 more += spaces - need;
    715                 less = a[j];
    716 
    717             }
    718 
    719             if (a[j] > i){
    720                 int need = a[j] - more - 1;
    721                 res *= comb.ncr(spaces, need);
    722                 less += spaces - need;
    723                 more = a[j];
    724             }
    725 
    726             spaces = 0;
    727         }
    728 
    729         res *= comb.ncr(spaces, i - less);
    730 
    731         ans += res;
    732     }
    733 
    734     bool sorted = true;
    735     for (int i = 0; i < n; i++){
    736         if (a[i] != i && a[i] != -1)
    737             sorted = false;
    738     }
    739 
    740     if (sorted)
    741         ans -= n - 2;
    742     cout << ans << "\n";
    743 }
    744 
    745 int main(){
    746     ios::sync_with_stdio(false);
    747     cin.tie(0);
    748     
    749     int t;
    750     cin >> t;
    751     while (t--) solve();
    752 }
    753 ```
    754 
    755 [2154F2 - Bombing (Hard Version)](/contest/2154/problem/F2 "Codeforces Round 1060 (Div. 2)"):
    756 
    757 **Step 1**
    758 
    759 Solve the easy version.
    760 
    761 **Step 2**
    762 
    763 If $p_i \lt i$ we know that $p_i$ must belong to the left side of the split, similarly if $p_i \gt i$ we know that $p_i$ must belong to the right side of the split.
    764 
    765 **Step 3**
    766 
    767 If a permutation p is a riffle shuffle of $[1,2,\ldots,n]$, then it will have three regions described by two integers $l, r$ as follows:
    768 
    769 * a prefix where for all $i$ ($1 \le i \le l$) we have $p_i = i$.
    770 * a suffix where for all $i$ ($r \le i \le n$) we have $p_i = i$.
    771 * a middle region where for all $i$ ($l \lt i \lt r$) we have $p_i \ne i$.
    772 
    773 See that the first region will all belong to the left side of the split, and the last region will all belong to the right side of the split. Additionally, we can deduce the side of the entire middle region from Step 2. There is a single edge case to this where $p$ is the sorted permutation.
    774 
    775 **Step 4**
    776 
    777 Suppose there is an index $i$ where $a_i \ne i$ and $a_i \ne -1$, or in other words, the sorted permutation is not valid. In this case, from Step 3, we can deduce the side of every element $i$ where $a_i \ne -1$.
    778 
    779 **Step 5**
    780 
    781 For the opposite case to Step 4 (i.e, the case where the sorted permutation is valid), can you think of a way to solve this?
    782 
    783 **Step 5.1**
    784 
    785 Can you find a closed form formula for the case where $p_i = -1$ for all $i$?
    786 
    787 **Step 5.2**
    788 
    789 There is almost a bijection between colouring an array in two colours and valid riffle shuffles of $[1,2,\ldots,n]$ with the sole edge case being the sorted permutation, which is counted $n - 1$ times, if we account for this we obtain the formula $2^n - n$.
    790 
    791 **Step 5.3**
    792 
    793 Now that we have a formula, from Step 3 we should just find the number of ways to fill each run of consecutive $-1$, leaving everything outside as the prefix and suffix as discussed in Hint 3. Solving a consecutive run of $-1$ is equivalent to solving the case in Step 5.1 on a smaller array. So we just solve each of these runs and sum to get the answer for this case.
    794 
    795 **Step 6**
    796 
    797 Now lets solve the same case as Step 4. For each $k$, consider a consecutive run of $-1$ and try to find the number of ways to fill it, lets try to find some nice properties for some cases. Let me introduce some notation, I will type each gap in the following way:
    798 
    799 * an $l \rightarrow l$ gap means the element immediately before the gap belongs to the left side of the split and the element after belongs to the left side of the split.
    800 * an $l \rightarrow r$ gap means the element immediately before the gap belongs to the left side of the split and the element after belongs to the right side of the split.
    801 * similar notation for $r \rightarrow l$ and $r \rightarrow r$.
    802 
    803 Now notice that for any $k$, the number of ways to fill an $l \rightarrow l$ or $r \rightarrow r$ gap will always be the same.
    804 
    805 **Step 7**
    806 
    807 For the $l \rightarrow r$ and $r \rightarrow l$ gaps, we have to get a bit more creative. The key thing to notice is that each $k$ will demand a unique number of elements from the left side of the split to be placed inside the gap. Now since the number of left elements must be between $0$ and the size of the gap, we can restrict the number of $k$ we need to consider to no more than the size of the gap!
    808 
    809 **Step 8**
    810 
    811 For each gap, calculate this range of valid $k$, and take the intersection of all the ranges. Now if we use a very similar implementation to the easy version of the problem but only consider $k$ within this range, and skipping $l \rightarrow l$ and $r \rightarrow r$ gaps by calculating their contribution separately, the problem will be solved. Since, say, the range of valid $k$ has size $x$, then the number of $l \rightarrow r$ and $r \rightarrow l$ gaps will be no more than approximately $n/x$, and so the final time complexity is $O(x \cdot n/x)$, which is $O(n)$.
    812 
    813 **Implementation(C++)**
    814 
    815 ```
    816 #include<bits/stdc++.h>
    817 using namespace std;
    818 typedef long long ll;
    819 #define debug(x) cout << #x << " = " << x << "\n";
    820 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
    821 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    822 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
    823 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
    824 
    825 const int MOD = 998244353;
    826 
    827 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged
    828 struct modnum {
    829     static constexpr bool is_big_mod = mod > numeric_limits<int>::max();
    830 
    831     using S = conditional_t<is_big_mod, ll, int>;
    832     using L = conditional_t<is_big_mod, __int128, ll>;
    833 
    834     S x;
    835 
    836     modnum() : x(0) {}
    837     modnum(ll _x) {
    838         _x %= static_cast<ll>(mod);
    839         if (_x < 0) { _x += mod; }
    840         x = _x;
    841     }
    842 
    843     modnum pow(ll n) const {
    844         modnum res = 1;
    845         modnum cur = *this;
    846         while (n > 0) {
    847             if (n & 1) res *= cur;
    848             cur *= cur;
    849             n /= 2;
    850         }
    851         return res;
    852     }
    853     modnum inv() const { return (*this).pow(mod-2); }
    854     
    855     modnum& operator+=(const modnum& a){
    856         x += a.x;
    857         if (x >= mod) x -= mod;
    858         return *this;
    859     }
    860     modnum& operator-=(const modnum& a){
    861         if (x < a.x) x += mod;
    862         x -= a.x;
    863         return *this;
    864     }
    865     modnum& operator*=(const modnum& a){
    866         x = static_cast<L>(x) * a.x % mod;
    867         return *this;
    868     }
    869     modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    870     
    871     friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    872     friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    873     friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    874     friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    875     
    876     friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    877     friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    878     friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }
    879 
    880     friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    881     friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
    882 };
    883 
    884 using mint = modnum<MOD>;
    885 
    886 struct Combi{
    887     vector<mint> _fac, _ifac;
    888     int n;
    889     
    890     Combi() {
    891         n = 1;
    892         _fac.assign(n + 1, 1);
    893         _ifac.assign(n + 1, 1);
    894     }
    895     
    896     void check_size(int m){
    897         int need = n;
    898         while (need < m) need *= 2;
    899         m = need;
    900         if (m <= n) return;
    901         
    902         _fac.resize(m + 1);
    903         _ifac.resize(m + 1);
    904         for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1];
    905         
    906         _ifac[m] = _fac[m].inv();
    907         for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
    908         n = m;
    909     }
    910     
    911     mint fac(int m){
    912         check_size(m);
    913         return _fac[m];
    914     }
    915     
    916     mint ifac(int m){
    917         check_size(m);
    918         return _ifac[m];
    919     }
    920     
    921     mint ncr(int n, int r){
    922         if (n < r || r < 0) return 0;
    923         
    924         return fac(n) * ifac(n - r) * ifac(r);
    925     }
    926     
    927     mint npr(int n, int r){
    928         if (n < r || r < 0) return 0;
    929         
    930         return fac(n) * ifac(n - r);
    931     }
    932 } comb;
    933 
    934 void solve(){
    935     int n;
    936     cin >> n;
    937 
    938     vector<int> a(n);
    939     for (int &x : a) {
    940         cin >> x;
    941         if (x != -1)
    942             x--;
    943     }
    944 
    945     bool fixed = true;
    946     for (int i = 0; i < n; i++)
    947         if (a[i] != -1 && a[i] != i)
    948             fixed = false;
    949 
    950     if (fixed){ //case where all a[i] != -1 has a[i] = i
    951         vector<mint> prod(n + 1);
    952         prod[0] = 1;
    953         for (int i = 1; i <= n; i++)
    954             prod[i] = prod[i - 1] * 2;
    955 
    956         int last = -1;
    957         mint ans = 0;
    958         for (int i = 0; i <= n; i++){
    959             if (i == n || a[i] != -1){
    960                 int len = i - last - 1;
    961                 ans += prod[len] - len - 1;
    962                 last = i;
    963             }
    964         }
    965 
    966         ans += 1;
    967         cout << ans << "\n";
    968         return;
    969     }
    970 
    971     vector<bool> side(n);
    972     bool found = false;
    973     for (int i = 0; i < n; i++){
    974         if (a[i] == -1)
    975             continue;
    976 
    977         if (a[i] < i)
    978             side[i] = false; // left side
    979         if (a[i] > i)
    980             side[i] = true; // right side
    981         if (a[i] == i)
    982             side[i] = found;
    983         if (a[i] != i)
    984             found = true;
    985     }
    986 
    987     int last = -1;
    988     vector<array<int, 2>> ranges;
    989     for (int i = 0; i < n; i++){
    990         if (a[i] == -1)
    991             continue;
    992         
    993         if (last == -1){
    994             last = i;
    995             continue;
    996         }
    997 
    998         if (side[i] && !side[last]){ // left -> right gap
    999             int mn = last - a[last]; // min right already placed
   1000             int mx = mn + i - last; // max right already placed
   1001             ranges.push_back({a[i] - mx, a[i] - mn + 1});
   1002         }
   1003 
   1004         if (!side[i] && side[last]){ // right -> left gap
   1005             int mx = i - a[i]; // max right placed by last
   1006             int mn = mx - (i - last); // min right placed by last
   1007             ranges.push_back({a[last] - mx, a[last] - mn + 1});
   1008         }
   1009 
   1010         last = i;
   1011     }
   1012 
   1013     int l = 0, r = n - 1;
   1014     for (auto [u, v] : ranges){
   1015         l = max(l, u);
   1016         r = min(r, v);
   1017     }
   1018 
   1019     mint coef = 1;
   1020     vector<mint> score(n); // score[i] = contribution when splitting at i
   1021     for (int i = l; i <= r; i++)
   1022         score[i] = 1;
   1023 
   1024     last = -1;
   1025     for (int i = 0; i < n; i++){
   1026         if (a[i] == -1)
   1027             continue;
   1028         
   1029         bool prev = false;
   1030         if (last != -1)
   1031             prev = side[last];
   1032         int spaces = i - last - 1;
   1033 
   1034         if (side[i] && prev || !side[i] && !prev){
   1035             int cnt = 0;
   1036             if (last == -1)
   1037                 cnt = a[i];
   1038             else
   1039                 cnt = a[i] - a[last] - 1;
   1040 
   1041             coef *= comb.ncr(spaces, cnt);
   1042         }
   1043 
   1044         if (side[i] && !prev){ // left -> right
   1045             for (int j = l; j <= r; j++){
   1046                 int placed = 0;
   1047                 if (last != -1)
   1048                     placed = last - a[last]; // how many right i have placed by last
   1049 
   1050                 int need = a[i] - (j + placed); // j + placed is the next one i need to place after last
   1051                 score[j] *= comb.ncr(spaces, need);
   1052             }
   1053         }
   1054 
   1055         if (!side[i] && prev){ // right -> left
   1056             for (int j = l; j <= r; j++){
   1057                 int big = i - a[i] + j - 1; // last right to be placed by i
   1058                 
   1059                 int need = big - a[last];
   1060                 score[j] *= comb.ncr(spaces, need);
   1061             }
   1062         }
   1063 
   1064         last = i;
   1065     }
   1066 
   1067     for (int j = l; j <= r; j++){
   1068         if (!side[last]){
   1069             score[j] *= comb.ncr(n - last - 1, j - a[last] - 1);
   1070         }
   1071         else{
   1072             score[j] *= comb.ncr(n - last - 1, n - 1 - a[last]);
   1073         }
   1074     }
   1075 
   1076     mint ans = 0;
   1077     for (int i = 0; i < n; i++)
   1078         ans += score[i];
   1079     ans *= coef;
   1080     cout << ans << "\n";
   1081 }
   1082 
   1083 int main(){
   1084     ios::sync_with_stdio(false);
   1085     cin.tie(0);
   1086     
   1087     int t;
   1088     cin >> t;
   1089     while (t--) solve();
   1090 }
   1091 ```
   1092 
   1093 Bonus editorial by [Friedrich](/profile/Friedrich "Master Friedrich"):
   1094 
   1095 **Solution 2**
   1096 
   1097 **Hint 1**
   1098 
   1099 Can you uniquely determine, for each element $a[i]$, which subsequence it belongs to?
   1100 
   1101 **Hint 2**
   1102 
   1103 For which values of $k$ does a solution exist?
   1104 
   1105 **Solution**
   1106 
   1107 Let the subsequence on indices $1$ to $k$ be $L$ and the subsequence on indices $k+1$ to $n$ be $R$.
   1108 
   1109 For every $a[i]\in L$ we have $a[i]-i\le 0$, since there must be exactly $a[i]-1$ elements of $L$ before position $i$. Symmetrically, for every $a[i]\in R$ we have $a[i]-i\ge 0$.
   1110 
   1111 From the same observation, if $a[i]\in L$ then there must be exactly $i-a[i]$ indices $j \lt i$ with $a[j]\in R$. This lets us decide the side of each element except when $a[i]=i$, which is ambiguous. Once there exists some $a[j]\ne j$, the counts of elements in $L$ and $R$ to the left and right are constrained and cannot both decrease, so within any interval between fixed points $a[i]=i$ both types $L$ and $R$ must appear unless the whole interval consists of fixed points.
   1112 
   1113 **First case.** There are positions with $a[i]=i$. Consider the gaps between consecutive fixed points. In a gap of size $m$ between indices $i$ and $j$ with $a[i]=i$ and $a[j]=j$, we can count the valid assignments of the elements $i+1,\dots,j-1$ to $L$ or $R$. Summing over all possible splits gives $\binom{m}{0}+\binom{m}{1}+\cdots+\binom{m}{m-1}=2^{m-1}.$ To avoid overcounting the fully ordered arrangement, for each gap of size $m$ we count $2^{m-1}-m-1$, and then add $1$ at the end for the completely ordered sequence.
   1114 
   1115 **Second case.** Every element can be assigned unambiguously to $L$ or $R$. Add a sentinel $a[0]=0$ and assign it to $L$. Track $n+1$ dynamic states $(i,j)$ with initial states $(1,1),(1,2),\dots,(1,n+1)$, where $i$ is the next index needed in $L$ and $j$ is the next index needed in $R$. Each state stores the number of ways to reach it, initially $1$.
   1116 
   1117 Updating every state at every step would be too slow, so only update at gap boundaries. There are two subcases for a gap of size $m$:
   1118 
   1119 1. The endpoints of the gap belong to the same side. For each state, we know how many of the $m$ elements, say $k$, must go to that side, so we multiply the state’s count by $\binom{m}{k}$ and advance $(i,j)$ accordingly by $k$ and $m-k$.
   1120 2. The endpoints belong to different sides. First apply any deferred updates. Now either $i$ or $j$ is identical across all current states because the last element before the gap was forced to $L$ or $R$. For a gap of size $m$ there are at most $m$ next states, and for each we can compute the number of shuffles since the counts assigned to $L$ and $R$ are fixed. This gives $O(m)$ work per gap, hence $O(n)$ overall.
   1121 
   1122 This completes the counting in $O(n)$ time.
   1123 
   1124 **Implementation(Python)**
   1125 
   1126 ```
   1127 import sys
   1128 input = sys.stdin.readline
   1129 MOD = 998244353
   1130 
   1131 fac_arr = [1]
   1132 finv_arr = [1]
   1133 
   1134 def enlarge_fac():
   1135     old_size = len(fac_arr)
   1136     new_size = old_size * 2
   1137     for i in range(old_size, new_size + 1):
   1138         fac_arr.append((fac_arr[-1] * i) % MOD)
   1139     ifac = [pow(fac_arr[-1], -1, MOD)]
   1140     for i in range(new_size, old_size,-1):
   1141         ifac.append((ifac[-1] * i) % MOD)
   1142     ifac.reverse()
   1143     for x in ifac:
   1144         finv_arr.append(x)
   1145 
   1146 def fac(n):
   1147     while n >= len(fac_arr): enlarge_fac()
   1148     return fac_arr[n]
   1149 
   1150 def finv(n):
   1151     while n >= len(finv_arr): enlarge_fac()
   1152     return finv_arr[n]
   1153 
   1154 def binom(n, k):
   1155     if k < 0 or k > n: return 0
   1156     return ((fac(n) * finv(k)) % MOD * finv(n - k)) % MOD
   1157 for _ in range(int(input())):
   1158     n = int(input())
   1159     a = list(map(int, input().split())) + [n+1]
   1160     if max([0 if a[i] == -1 else abs(a[i]-i-1) for i in range(n)]) == 0:
   1161         sol = 1
   1162         last = 0
   1163         for i in a:
   1164             if i >= 0:
   1165                 sol += pow(2, i - last - 1, MOD) - 1 - (i - last - 1)
   1166                 last = i
   1167                 sol %= MOD
   1168         print(sol)
   1169     else:
   1170         S = [(0,i,1) for i in range(1,n)]
   1171         last = -1
   1172         left = 1
   1173         eq = 0
   1174         pl = 0
   1175         mult = 1
   1176         lastv = 0
   1177         nd = 0
   1178         for idx in range(n+1):
   1179             if a[idx] == -1: continue
   1180             gap = idx - last - 1
   1181             at = 0
   1182             if idx + 1 > a[idx] or (idx + 1 == a[idx] and eq == 0):
   1183                 if idx + 1 > a[idx]: eq = 1
   1184                 at = 1
   1185             else: eq = 1
   1186             TMP = []
   1187             if at ^ left:
   1188                 for i,j,k in S:
   1189                     if left: j += pl; i = nd
   1190                     else: i += pl; j = nd
   1191                     if left: rev = a[idx] - j - 1
   1192                     else: rev = a[idx] - i - 1
   1193                     if left: i += gap - rev
   1194                     else: j += gap - rev
   1195                     if at: i = a[idx]
   1196                     else: j = a[idx]
   1197                     f = binom(gap,rev)
   1198                     if f: TMP.append((i,j,(k*f)%MOD))
   1199                 left ^= 1
   1200                 pl = 0
   1201                 lastv = a[idx]
   1202                 nd = a[idx]
   1203                 S = TMP
   1204             else:
   1205                 rev = a[idx] - lastv - 1
   1206                 pl += gap - rev
   1207                 nd = a[idx]
   1208                 lastv = a[idx]
   1209                 mult *= binom(gap,rev)
   1210                 mult %= MOD
   1211             last = idx
   1212         print(((sum([x[-1] for x in S])%MOD)*mult)%MOD)
   1213 ```