codeforces-scrape

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

1827.md (36028B)


      1 Source: https://codeforces.com/blog/entry/116109
      2 
      3 ## [1828A - Divisible Array](/contest/1828/problem/A "Codeforces Round 873 (Div. 2)")
      4 
      5 Idea: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi")   
      6  Preparation: [Mike4235](/profile/Mike4235 "Master Mike4235")
      7 
      8 **Hint 1**
      9 
     10 Remember the sum of the first $n$ positive integers?
     11 
     12 **Hint 2**
     13 
     14 Every positive integer is divisible by $1$.
     15 
     16 **Solution**
     17 
     18 Consider the array $a = \left[1, 2, \ldots, n\right]$ that satisfies the second condition. It has the sum of $1 + 2 + \dots + n = \frac{n(n+1)}{2}$.
     19 
     20 One solution is to notice that if we double every element $(a=\left[2, 4, 6, \ldots, 2n\right])$, the sum becomes $\frac{n(n+1)}{2} \times 2 = n(n + 1)$, which is divisible by $n$.
     21 
     22 Another solution is to increase the value of $a_1$ until the sum becomes divisible by $n$. This works because every integer is divisible by $1$, and we only need to increase $a_1$ by at most $n$.
     23 
     24 Time complexity: $\mathcal{O}(n)$
     25 
     26 **Implementation 1**
     27 
     28 ```
     29 #include <bits/stdc++.h>
     30  
     31 using namespace std;
     32  
     33 int main() {
     34     
     35     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     36  
     37     int t;
     38     cin >> t;
     39     while (t--) {
     40     	int n;
     41     	cin >> n;
     42     	for (int i = 1; i <= n; i++) cout << i * 2 << " ";
     43     	cout << "\n";
     44     }
     45 }
     46 ```
     47 
     48 **Implementation 2**
     49 
     50 ```
     51 #include<bits/stdc++.h>
     52 using namespace std;
     53 typedef long long ll;
     54 #define fi first
     55 #define se second
     56 const int N=2e6+1;
     57 const ll mod=998244353;
     58 ll n,m;
     59 ll a[N],b[N];
     60 void solve(){
     61 	cin >> n;
     62 	ll s=0;
     63 	for(int i=n; i>=2 ;i--){
     64 		a[i]=i;
     65 		s=(s+i)%n;
     66 	}
     67 	a[1]=n-s;
     68 	for(int i=1; i<=n ;i++) cout << a[i] << ' ';
     69 	cout << '\n';
     70 }
     71 int main(){
     72 	ios::sync_with_stdio(false);cin.tie(0);
     73 	int t;cin >> t;
     74 	while(t--){
     75 		solve();
     76 	}
     77 }
     78 ```
     79 
     80 ## [1828B - Permutation Swap](/contest/1828/problem/B "Codeforces Round 873 (Div. 2)")
     81 
     82 Idea: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi")   
     83  Preparation: [Mike4235](/profile/Mike4235 "Master Mike4235")
     84 
     85 **Hint 1**
     86 
     87 In order to move $p_i$ to its right position, what does the value of $k$ have to satisfy?
     88 
     89 **Solution**
     90 
     91 In order to move $p_i$ to position $i$, it is easy to see that $|p_i - i|$ has to be divisible by $k$.
     92 
     93 So, $|p_1 - 1|, |p_2 - 2|, \ldots, |p_n - n|$ has to be all divisible by $k$. The largest possible value of $k$ turns out to be the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $|p_1 - 1|, |p_2 - 2|, \ldots, |p_n - n|$.
     94 
     95 Time complexity: $\mathcal{O}(n + \log{n})$
     96 
     97 **Implementation**
     98 
     99 ```
    100 #include <bits/stdc++.h>
    101  
    102 using namespace std;
    103  
    104 signed main() {
    105     
    106     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    107  
    108     int t;
    109     cin >> t;
    110     while (t--) {
    111     	int n, res = 0;
    112     	cin >> n;
    113     	for (int i = 1; i <= n; i++) {
    114     		int x; cin >> x;
    115     		res = __gcd(res, abs(x - i));
    116     	}
    117     	cout << res << "\n";
    118     }
    119     
    120 }
    121 ```
    122 
    123 ## [1827A - Counting Orders](/contest/1827/problem/A "Codeforces Round 873 (Div. 1)")
    124 
    125 Idea: [Mike4235](/profile/Mike4235 "Master Mike4235")   
    126  Preparation: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi")
    127 
    128 **Hint 1**
    129 
    130 Sort the array $b$, and fix the values from $a_n$ to $a_1$.
    131 
    132 **Solution**
    133 
    134 First, we can sort the array $b$, as it does not change the answer.
    135 
    136 Let's try to choose the values of $a$ from $a_n$ to $a_1$. How many ways are there to choose the value of $a_i$?
    137 
    138 The new $a_i$ must satisfies $a_i \gt b_i$. But some of the candidates are already chosen as $a_j$ for some $j \gt i$. However, since $a_j \gt b_j \ge b_i$, we know that there are exactly $(n - i)$ candidates already chosen previously by all values of $j \gt i$. So, there are (number of $k$ such that $a_k \gt b_i$) $- (n - i)$ ways to choose the value of $a_i$.
    139 
    140 We can use two pointers or binary search to efficiently find the (number of $k$ such that $a_k \gt b_i$) for all $i$.
    141 
    142 Time complexity: $\mathcal O(n \log n)$.
    143 
    144 **Implementation**
    145 
    146 ```
    147 #include <bits/stdc++.h>
    148 using namespace std;
    149 typedef long long ll;
    150 const int MOD = 1e9 + 7;
    151 
    152 struct testcase{
    153     testcase(){
    154         int n; cin >> n;
    155         vector<int> a(n);
    156         for (int i=0; i<n; i++) cin >> a[i];
    157         sort(a.begin(), a.end());
    158         vector<int> b(n);
    159         for (int i=0; i<n; i++) cin >> b[i];
    160         sort(b.begin(), b.end(), greater<>());
    161         ll result = 1;
    162         for (int i=0; i<n; i++){
    163             int geq_count = a.size() - (upper_bound(a.begin(), a.end(), b[i]) - a.begin());
    164             result = result * max(geq_count - i, 0) % MOD;
    165         }
    166         cout << result << "\n";
    167     }
    168 };
    169 
    170 signed main(){
    171     cin.tie(0)->sync_with_stdio(0);
    172     int t; cin >> t;
    173     while (t--) testcase();
    174 }
    175 ```
    176 
    177 ## [1827B2 - Range Sorting (Hard Version)](/contest/1827/problem/B2 "Codeforces Round 873 (Div. 1)")
    178 
    179 Idea: [lanhf](/profile/lanhf "Master lanhf")   
    180  Preparation: [Mike4235](/profile/Mike4235 "Master Mike4235")
    181 
    182 **Hint 1**
    183 
    184 What is the minimum cost to sort just one subarray?
    185 
    186 **Hint 2**
    187 
    188 What happens when two operations intersect each other?
    189 
    190 **Hint 3**
    191 
    192 When can we sort two adjacency ranges independently?
    193 
    194 **Hint 4**
    195 
    196 Try to calculate the contribution of each position.
    197 
    198 **Solution**
    199 
    200 Let $a[l..r]$ denotes the subarray $a_l,a_{l+1},\ldots,a_r$.
    201 
    202 **Observation 1**: In an optimal sequence of operations for one subarray, there will be no two operations that intersect each other. In other words, a subarray will be divided into non-overlapping subarrays, and we will apply a range-sort operation to each subarray.
    203 
    204 *Proof*: Suppose there are two operations $[l_1,r_1]$ and $[l_2,r_2]$ that intersect each other, we can replace them with one operation $[\min(l_1,l_2),\max(r_1,r_2)]$ which does not increase the cost.
    205 
    206 **Observation 2**: Consider $k$ positions $l\le i_1 \lt i_2 \lt \ldots \lt i_k \lt r$, then we can sort subarrays $a[l..i_1],$ $a[i_1+1..i_2],$ $\ldots,$ $a[i_k+1..r]$ independently iff $\max(a[l..i_x]) \lt \min(a[i_x+1..r])$ for all $1\le x\le k$.
    207 
    208 *Proof*: The obvious necessary and sufficient condition required to sort subarrays $a[l..i_1],$ $a[i_1+1..i_2],$ $\ldots,$ $a[i_k+1..r]$ independently is $\max(a[i_{x-1}+1..i_x]) \lt \min(a[i_x+1..i_{x+1}])$ for all $1\le x\le k$, here we denote $x_0=l-1$ and $x_{k+1}=r$. It is not hard to prove that this condition is equal to the one stated above.
    209 
    210 With these observations, we can conclude that the answer for a subarray $a[l..r]$ equals the $r-l$ minus the number of positions $k$ such that $l\le k\lt r$ and $\max(a[l..k]) \lt \min(a[k+1..r])$ $(*)$. Let us analyze how to calculate the sum of this value over all possible $l$ and $r$.
    211 
    212 Consider a position $i$ ($1\le i\le n$), let's count how many triplets $(l, k, r)$ satisfy $(*)$ and $min(a[k+1..r]) = a_i$. It means that $k$ must be the closest position to the left of $i$ satisfying $a_k \lt a_i$. Denotes $x$ as the closest position to the left of $k$ such that $a_x \gt a_i$, and $y$ as the closest position to the right of $i$ such that $a_y \lt a_i$.
    213 
    214 We can see that a triplet $(l, k, r)$ with $x \lt l\le k$ and $i\le r \lt y$ will match our condition. In other words, we will add to the answer $(k - x) \cdot (y - i)$.
    215 
    216 In the easy version, we can find such values of $x, k, y$ for each $i$ in $\mathcal{O}(n)$ and end up with a total complexity of $O(n^2)$. We can further optimize the algorithm by using sparse table and binary lifting and achieve a time complexity of $\mathcal{O}(n \log{n})$, which is enough to solve the hard version.
    217 
    218 There is an $\mathcal{O}(n)$ solution described [here](https://codeforces.com/blog/entry/116109?#comment-1029986).
    219 
    220 **Implementation 1**
    221 
    222 ```
    223 #include <bits/stdc++.h>
    224 
    225 using namespace std;
    226 
    227 const int N = 500005;
    228 const int LOG = 19;
    229 
    230 int a[N], r[N], rmq[LOG][N];
    231 
    232 void solve() {
    233   int n; cin >> n;
    234   long long res = 0;
    235   vector<int> s;
    236   a[0] = a[n + 1] = 0;
    237   for (int i = 1; i <= n; i++) {
    238     cin >> a[i];
    239     rmq[0][i] = a[i];
    240     res += 1ll * i * (i - 1) / 2;
    241   }
    242   s.push_back(n + 1);
    243   for (int i = n; i > 0; i--) {
    244     while (a[s.back()] > a[i])
    245       s.pop_back();
    246     r[i] = s.back();
    247     s.push_back(i);
    248   }
    249   for (int k = 1; k < LOG; k++)
    250     for (int i = (1 << k); i <= n; i++)
    251       rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i - (1 << (k - 1))]);
    252   s.clear();
    253   s.push_back(0);
    254   for (int i = 1; i <= n; i++) {
    255     while (a[s.back()] > a[i])
    256       s.pop_back();
    257     int j = s.back();
    258     for (int k = LOG - 1; k >= 0; k--)
    259       if (j >= (1 << k) && rmq[k][j] < a[i])
    260         j -= 1 << k;
    261     res -= 1ll * (r[i] - i) * (s.back() - j);
    262     s.push_back(i);
    263   }
    264   cout << res << '\n';
    265 }
    266 
    267 int main() {
    268   cin.tie(0)->sync_with_stdio(0);
    269   int t; cin >> t;
    270   while (t--) solve();
    271 }
    272 ```
    273 
    274 **Implementation 2**
    275 
    276 ```
    277 #include <bits/stdc++.h>
    278 using namespace std;
    279 
    280 const int N = 3e5 + 5;
    281 
    282 int n;
    283 int a[N];
    284 
    285 pair <int, int> b[N];
    286 
    287 signed main(){
    288     ios_base::sync_with_stdio(0);
    289     cin.tie(0); cout.tie(0);
    290 int tests; cin >> tests; while (tests--){
    291     cin >> n;
    292     for (int i = 1; i <= n; i++){
    293         cin >> a[i];
    294     }
    295 
    296     for (int i = 1; i <= n; i++){
    297         b[i] = make_pair(a[i], i);
    298     }
    299     sort(b + 1, b + n + 1);
    300 
    301     set <int> sttlo = {0, n + 1}, stthi = {0, n + 1};
    302     for (int i = 1; i <= n; i++){
    303         stthi.emplace(i);
    304     }
    305     long long ans = 0;
    306     for (int len = 1; len <= n; len++){
    307         ans += (long long)(len - 1) * (n - len + 1);
    308     }
    309     for (int i = 1; i <= n; i++){
    310         int idx = b[i].se;
    311         stthi.erase(idx); sttlo.emplace(idx);
    312  
    313         int x2 = *stthi.lower_bound(idx);
    314         int x1 = *prev(stthi.lower_bound(idx));
    315         if (x2 == n + 1){
    316             continue;
    317         }
    318         int x3 = *sttlo.lower_bound(x2);
    319         ans -= (long long)(idx - x1) * (x3 - x2);
    320     }
    321     cout << ans << endl;
    322 }
    323 }
    324 ```
    325 
    326 **Bonus**
    327 
    328 Solve the problem when the beauty of an array is (minimum time needed to sort)$^2$.
    329 
    330 ## [1827C - Palindrome Partition](/contest/1827/problem/C "Codeforces Round 873 (Div. 1)")
    331 
    332 Idea: [lanhf](/profile/lanhf "Master lanhf")   
    333  Preparation: [lanhf](/profile/lanhf "Master lanhf")
    334 
    335 **Hint1**
    336 
    337 Try to construct beautiful string greedily.
    338 
    339 **Hint2**
    340 
    341 What happens when we have two even palindromes share one of their endpoints?
    342 
    343 **Solution**
    344 
    345 For the simplicity of the solution, we will abbreviate even palindrome as evp.
    346 
    347 **Lemma**: Consider a beautiful string $t$, we can find the **unique maximal** partition for it by greedily choosing the smallest possible evp in each step from the left. Here maximal means maximum number of parts.
    348 
    349 *Proof*: Suppose $t[0..l)$ is smallest prefix which is an evp and $t[0..r)$ is the first part in the partition of $t$, here $t[l..r)$ mean substring $t_l t_{l+1}\ldots t_{r-1}$. We consider two cases:
    350 
    351 * $2l\le r$: In this case, it is clear that $t[0..l)$, $t[l..r - l)$ and $t[r-l..r)$ are evps, so we can replace $t[0..r)$ with them.
    352 
    353 ![ ](/predownloaded/fc/5c/fc5c9b76212e5a482bd0ac46af18997696478db2.png)
    354 
    355 * $2l \gt r$: In this case, due to the fact that $t[r-l..l)$ and $t[0..l)$ are evps, $t[0..2l-r)$ is also an evp, which contradicts to above assumption that $t[0..l)$ is the smallest.
    356 
    357 ![ ](/predownloaded/a9/ed/a9ed97d93b212c442080880ff7e81b620117ebb9.png)
    358 
    359 We can use dynamic programming to solve this problem. Let $dp_i$ be the number of beautiful substrings starting at $i$. For all $i$ from $n-1$ to $0$, if there are such $next_i$ satisfying $s[i..next_i)$ is the smallest evp beginning at $i$, then $dp_i=dp_{next_i}+1$, otherwise $dp_i=0$. The answer will be the sum of $dp_i$ from $0$ to $n-1$.
    360 
    361 To calculate the $next$ array, first, we use Manacher algorithm or hashing to find the maximum $pal_i$ satisfying $s[i-pal_i..i+pal_i)$ is an evp for each $i$. Then for all $0\le i \lt n$, $next_i=2j-i$ where $j$ is smallest position such that $i \lt j$ and $j-pal_j\le i$. The time complexity is $\mathcal{O}(n \log{n})$.
    362 
    363 **Implementation**
    364 
    365 ```
    366 #include <bits/stdc++.h>
    367  
    368 using namespace std;
    369  
    370 const int N = 500005;
    371 const int LOG = 19;
    372  
    373 int n, pal[N], rmq[LOG][N], cnt[N];
    374 string s;
    375  
    376 int main() {
    377   cin.tie(0)->sync_with_stdio(0);
    378   int t; cin >> t;
    379   while (t--) {
    380     cin >> n >> s;
    381     for (int i = 0, l = 0, r = 0; i < n; i++) {
    382       pal[i] = i >= r ? 0 : min(pal[l + r - i], r - i);
    383       while (i + pal[i] < n && i - pal[i] - 1 >= 0
    384       && s[i + pal[i]] == s[i - pal[i] - 1]) pal[i]++;
    385       if (i + pal[i] > r) {
    386         l = i - pal[i]; r = i + pal[i];
    387       }
    388     }
    389     for (int i = 0; i < n; i++)
    390       rmq[0][i] = i - pal[i];
    391     for (int k = 1; k < LOG; k++)
    392       for (int i = 0; i + (1 << k) <= n; i++)
    393         rmq[k][i] = min(rmq[k - 1][i],
    394         rmq[k - 1][i + (1 << (k - 1))]);
    395     for (int i = 1; i <= n; i++)
    396       cnt[i] = 0;
    397     for (int i = 0; i < n; i++) {
    398       int j = i + 1;
    399       for (int k = LOG - 1; k >= 0; k--)
    400         if (j + (1 << k) <= n && rmq[k][j] > i)
    401           j += 1 << k;
    402       if (2 * j - i <= n)
    403         cnt[2 * j - i] += cnt[i] + 1;
    404       
    405     }
    406     long long res = 0;
    407     for (int i = 1; i <= n; i++)
    408       res += cnt[i];
    409     cout << res << '\n';
    410   }
    411 }
    412 ```
    413 
    414 **Bonus**
    415 
    416 Solve the problem in $\mathcal{O}(n)$.
    417 
    418 ## [1827D - Two Centroids](/contest/1827/problem/D "Codeforces Round 873 (Div. 1)")
    419 
    420 Idea: [Mike4235](/profile/Mike4235 "Master Mike4235")   
    421  Preparation: [lanhf](/profile/lanhf "Master lanhf")
    422 
    423 **Hint1**
    424 
    425 Is the answer related to the centroid of the current tree?
    426 
    427 **Hint2**
    428 
    429 How much the centroid will move after one query?
    430 
    431 **Solution**
    432 
    433 **Observation**: The answer for the tree with $n$ vertices equals $n-2\cdot mx$ where $mx$ is the largest subtree among the centroid's children.
    434 
    435 **Lemma**: After one query, the centroid will move at most one edge, and when the centroid move, the tree before the query already has two centroids.
    436 
    437 *Proof*:
    438 
    439 ![ ](/predownloaded/31/37/3137e7aecc401518590227df55a6bea148dc6bb7.png)
    440 
    441 Suppose the tree before the query has $n$ vertices and the current centroid is $u$. Let $v_1, v_2,\ldots,v_k$ are the children of $u$ and the next query vertex $x$ is in subtree $v_1$. Clearly, the centroid is either $u$ or in the subtree $v_1$. Consider the latter case, because the size of subtree $v_1$ does not greater than $\lfloor \frac{n}{2}\rfloor$, the size of newly formed subtree including $u$ is greater or equal to $\lceil \frac{n}{2}\rceil$. Moving one or more edges away from $v_1$ will increase the size of this new subtree by one or more, and the vertex can not become centroid because $\lceil \frac{n}{2}\rceil+1 \gt \lfloor \frac{n+1}{2}\rfloor$.
    442 
    443 The second part is easy to deduce from the above proof.
    444 
    445 We will solve this problem offline. First, we compute the Euler tour of the final tree and use "range add query" data structures like Binary indexed tree (BIT) or Segment tree to maintain each subtree's size. We will maintain the size of the largest subtree among the centroid's children $mx$. In the case where the centroid does not move, we just update $mx$ with the size of the subtree including the newly added vertex, otherwise, we set $mx$ to $\lfloor \frac{n}{2}\rfloor$ due to the lemma. The time complexity is $\mathcal{O}(n \log{n})$.
    446 
    447 **Implementation**
    448 
    449 ```
    450 #include <bits/stdc++.h>
    451 
    452 using namespace std;
    453 
    454 const int N = 500005;
    455 const int LOG = 19;
    456 
    457 vector<int> adj[N];
    458 int tin[N], tout[N], timer;
    459 int par[LOG][N], bit[N], dep[N];
    460 
    461 void dfs(int u) {
    462   tin[u] = ++timer;
    463   dep[u] = dep[par[0][u]] + 1;
    464   for (int k = 1; k < LOG; k++)
    465     par[k][u] = par[k - 1][par[k - 1][u]];
    466   for (int v : adj[u]) dfs(v);
    467   tout[u] = timer;  
    468 }
    469 
    470 void add(int u) {
    471   for (int i = tin[u]; i < N; i += i & -i)
    472     bit[i]++;
    473 }
    474 
    475 int get(int u) {
    476   int res = 0;
    477   for (int i = tout[u]; i > 0; i -= i & -i)
    478     res += bit[i];
    479   for (int i = tin[u] - 1; i > 0; i -= i & -i)
    480     res -= bit[i];
    481   return res;
    482 }
    483 
    484 int jump(int u, int d) {
    485   for (int k = 0; k < LOG; k++)
    486     if (d >> k & 1) u = par[k][u];
    487   return u;
    488 }
    489 
    490 bool cover(int u, int v) {
    491   return tin[u] <= tin[v] && tin[v] <= tout[u];
    492 }
    493 
    494 void solve() {
    495   int n; cin >> n;
    496   
    497   /// reset
    498   timer = 0;
    499   for (int i = 1; i <= n; i++) {
    500     bit[i] = 0; adj[i].clear();
    501   }
    502   
    503   for (int i = 2; i <= n; i++) {
    504     cin >> par[0][i];
    505     adj[par[0][i]].push_back(i);
    506   }
    507   dfs(1); add(1);
    508   int cen = 1, max_siz = 0;
    509   for (int u = 2; u <= n; u++) {
    510     add(u);
    511     if (cover(cen, u)) {
    512       int v = jump(u, dep[u] - dep[cen] - 1);
    513       int siz = get(v);
    514       if (siz >= (u + 1) / 2) {
    515         cen = v; max_siz = u / 2;
    516       } else max_siz = max(max_siz, siz);
    517     } else {
    518       int siz = get(cen);
    519       if (siz < (u + 1) / 2) {
    520         cen = par[0][cen]; max_siz = u / 2;
    521       } else max_siz = max(max_siz, u - siz);
    522     }
    523     cout << u - 2 * max_siz << " \n"[u == n];
    524   }
    525 }
    526 
    527 int main() {
    528   cin.tie(0)->sync_with_stdio(0);
    529   int t; cin >> t;
    530   while (t--) solve();
    531 }
    532 ```
    533 
    534 **flowerletter :pensive:**
    535 
    536 ![ ](/predownloaded/d6/df/d6dfc57989df440e6fe178c3d248b9116a75fad8.png)
    537 
    538 ## [1827E - Bus Routes](/contest/1827/problem/E "Codeforces Round 873 (Div. 1)")
    539 
    540 Idea: [Mike4235](/profile/Mike4235 "Master Mike4235")   
    541  Preparation: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi")
    542 
    543 **Hint 1**
    544 
    545 You do not need to consider all pairs of nodes, only some of them will do.
    546 
    547 **Hint 2**
    548 
    549 Find an equivalent condition of the statement.
    550 
    551 **Hint 2.1**
    552 
    553 Let $S(u)$ be the set of all nodes reachable by u using at most one route. Consider all $S(l)$ where $l$ is a leaf in the tree.
    554 
    555 **Solution**
    556 
    557 First, notice that for a pair of nodes $(u, v)$ such that $u$ is not a leaf, we can find a leaf $l$ such that path $(l, v)$ fully covers path $(u, v)$. Therefore, we only need to care about whether all pairs of leaves can reach each other using at most $2$ routes.
    558 
    559 **Lemma**
    560 
    561 The condition above is equivalent to: There exists a node $c$ such that $c$ can reach all leaves by using at most one route.
    562 
    563 *Proof*
    564 
    565 The necessity part is trivial, so let's prove the sufficiency part.
    566 
    567 Let the leaves of the tree be $l_1, l_2, \ldots, l_m$.
    568 
    569 Let $S(u)$ be the induced subgraph of all nodes reachable by $u$ using at most one route. If $u$ and $v$ is reachable within two routes, then the intersection of $S(v)$ and $S(u)$ is non-empty. We need to prove that the intersection of all $S(l_i)$ is non-empty.
    570 
    571 If $l_i$, $l_j$, and $l_k$ are pairwise reachable within two paths, then the intersection of $S(l_i)$, $S(l_j)$, and $S(l_k)$ must be pairwise non-empty. Since the graph is a tree, it follows trivially that intersection of $S(l_i)$, $S(l_j)$, and $S(l_k)$ must be non-empty. We can generalize this to all leaves, thus proving the sufficiency part.
    572 
    573 To check if an answer exists or not, we can use this [trick from ko_osaga](https://codeforces.com/blog/entry/51740?#comment-356857) to find how many $S(l_i)$ covers each node in $\mathcal O(n)$. The answer is YES when there is a node $c$ that is covered by all $S(l_i)$.
    574 
    575 To find the two candidates when the answer is NO, notice that one of them is the first leaf $l_x$ such that there is no node $c$ that is covered by $S(l_1), \ldots, S(l_x)$. We can find $l_x$ with binary search. To find the other one, root the tree at $l_x$ and define $lift_u$ as the lowest node reachable by $u$ using at most one route. The other candidate is a node $l_y$ such that $lift_{l_y}$ is not in $S(l_x)$.
    576 
    577 Time complexity: $\mathcal O(n \log n)$.
    578 
    579 Tester's solution: Root the tree at some non-leaf vertex. Define $lift_u$ as the lowest node (minimum depth) reachable by $u$ using at most one route. Take the node $v$ with the deepest (maximum depth) $lift_v$. Then the answer for this problem is $\texttt{YES}$ iff for every leaf $l$, either $l$ lie in $lift_v$ 's subtree or $l$ has a path to $lift_v$.
    580 
    581 **Implementation 1**
    582 
    583 ```
    584 #include <bits/stdc++.h>
    585 
    586 using namespace std;
    587 
    588 const int N = 5e5 + 5;
    589 const int LOG = 19;
    590 
    591 /// lca stuff
    592 int tin[N], timer = 0;
    593 vector<int> path, rmq[LOG];
    594 
    595 /// some tree stuff
    596 vector<int> adj[N], leaf, topo;
    597 int n, m, par[N], val[N];
    598 
    599 /// trips
    600 vector<int> trip[N];
    601 
    602 void dfs_pre(int u) {
    603   topo.push_back(u);
    604   tin[u] = timer++;
    605   for (int v : adj[u])
    606      if (v != par[u]) {
    607       path.push_back(u);
    608       rmq[0].push_back(tin[u]);
    609       par[v] = u; dfs_pre(v);
    610      }
    611 }
    612 
    613 int get_min(int l, int r) {
    614   int k = 31 - __builtin_clz(r - l);
    615   return min(rmq[k][l], rmq[k][r - (1 << k)]);
    616 }
    617 
    618 int lca(int u, int v) {
    619   if (u == v) return u;
    620   tie(u, v) = minmax(tin[u], tin[v]);
    621   return path[get_min(u, v)];
    622 }
    623 
    624 int lca_reroot(int r, int u, int v) {
    625   return lca(r, u) ^ lca(r, v) ^ lca(u, v);
    626 }
    627 
    628 void calc_val() {
    629   for (int u : topo)
    630     for (int v : adj[u])
    631       if (v != par[u]) val[u] += val[v];
    632 }
    633 
    634 void add(int u) {
    635   for (int v : trip[u])
    636     if (v < 0) val[-v]--;
    637     else val[v]++;
    638 }
    639 
    640 bool check(int l) {
    641   for (int u = 1; u <= n; u++) val[u] = 0;
    642   for (int i = 0; i < l; i++) add(leaf[i]);
    643   calc_val();
    644   for (int u = 1; u <= n; u++)
    645     if (val[u] == l) return true;
    646   return false;
    647 }
    648 
    649 void solve() {
    650   cin >> n >> m;
    651     
    652   /// reset 
    653   for (int i = 1; i <= n; i++) {
    654     adj[i].clear(); trip[i].clear();
    655   }
    656   timer = 0; leaf.clear(); topo.clear();
    657   path.clear(); rmq[0].clear();
    658 
    659   for (int i = 1; i < n; i++) {
    660     int u, v; cin >> u >> v;
    661     adj[u].push_back(v);
    662     adj[v].push_back(u);
    663   }
    664   /// leaves only
    665   for (int i = 1; i <= m; i++) {
    666     int u, v; cin >> u >> v;
    667     if (adj[u].size() == 1)
    668       trip[u].push_back(v);
    669     if (adj[v].size() == 1)
    670       trip[v].push_back(u);
    671   }
    672   
    673   if (n == 1) {
    674     cout << "YES\n"; return;
    675   }
    676   
    677   /// prepare
    678   dfs_pre(1);
    679   reverse(topo.begin(), topo.end());
    680   for (int k = 1; (1 << k) <= n; k++) {
    681     rmq[k].resize(n - (1 << k) + 1);
    682     for (int i = 0; i + (1 << k) <= n; i++)
    683       rmq[k][i] = min(rmq[k - 1][i],
    684       rmq[k - 1][i + (1 << (k - 1))]);
    685   }
    686   
    687   for (int u = 1; u <= n; u++)
    688     if (adj[u].size() == 1) {
    689       leaf.push_back(u);
    690       trip[u].push_back(u);
    691       sort(trip[u].begin(), trip[u].end(),
    692       [&](int x, int y) {
    693         return tin[x] < tin[y];});
    694       int l = trip[u].size();
    695       for (int i = 0; i + 1 < l; i++)
    696         trip[u].push_back(-lca
    697         (trip[u][i], trip[u][i + 1]));
    698       trip[u].push_back(-par[lca
    699       (trip[u][0], trip[u][l - 1])]);
    700     }
    701   
    702   /// find longest prefix of leaves 
    703   int l = 0;
    704   for (int k = LOG - 1; k >= 0; k--)
    705     if (l + (1 << k) <= leaf.size()
    706     && check(l + (1 << k))) l += 1 << k;
    707 
    708   if (l == leaf.size()) {
    709     cout << "YES\n"; return;
    710   }
    711   
    712   cout << "NO\n";
    713 
    714   for (int u = 1; u <= n; u++) val[u] = 0;
    715   add(leaf[l]); calc_val();
    716   
    717   for (int u : leaf) {
    718     bool good = false;
    719     for (int v : trip[u]) {
    720       if (v <= 0) break;
    721       if (val[lca_reroot(leaf[l], u, v)]) {
    722         good = true; break;
    723       }
    724     }
    725     if (!good) {
    726       cout << leaf[l] << ' ' << u << '\n';
    727       return;
    728     }
    729   }
    730 }
    731 
    732 int main() {
    733   cin.tie(0)->sync_with_stdio(0);
    734   
    735   int t; cin >> t;
    736   
    737   while (t--) solve();
    738 }
    739 ```
    740 
    741 **Implementation 2**
    742 
    743 ```
    744 #include<bits/stdc++.h>
    745 
    746 using namespace std;
    747 
    748 typedef long long ll;
    749 const ll INF = 1e18;
    750 const int maxn = 2e6 + 10;
    751 const int mod = 1e9 + 7;
    752 const int mo = 998244353;
    753 using pi = pair < ll, ll > ;
    754 using vi = vector < ll > ;
    755 using pii = pair < pair < ll, ll > , ll > ;
    756 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    757 vector < int > G[maxn];
    758 int n, m;
    759 int h[maxn];
    760 int eu[maxn];
    761 pair < int, int > rmq[maxn][21];
    762 int l = 0;
    763 int st[maxn];
    764 int out[maxn];
    765 int low[maxn];
    766 pair < int, int > ed[maxn];
    767 int par[maxn];
    768 int ok[maxn];
    769 int d[maxn];
    770 void dfs(int u, int pa) {
    771   eu[++l] = u;
    772   st[u] = l;
    773   for (auto v: G[u]) {
    774     if (v == pa) continue;
    775     par[v] = u;
    776     h[v] = h[u] + 1;
    777     dfs(v, u);
    778     eu[++l] = u;
    779   }
    780   out[u] = l;
    781 }
    782 void init() {
    783   for (int j = 1; (1 << j) <= l; j++) {
    784     for (int i = 1; i <= l; i++) {
    785       rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    786     }
    787   }
    788 }
    789 int LCA(int u, int v) {
    790   if (st[u] > st[v]) {
    791     swap(u, v);
    792   }
    793   int k = log2(st[v] - st[u] + 1);
    794   return min(rmq[st[u]][k], rmq[st[v] - (1 << k) + 1][k]).second;
    795 }
    796 bool check(int u, int pa, int c) {
    797   if (st[pa] <= st[c] && st[c] <= out[pa]) {
    798     if (st[c] <= st[u] && st[u] <= out[c]) {
    799       return true;
    800     }
    801     return false;
    802   }
    803   return false;
    804 }
    805 void solve() {
    806   cin >> n >> m;
    807   l = 0;
    808   for (int i = 1; i <= n; i++) {
    809     G[i].clear();
    810   }
    811   for (int i = 1; i < n; i++) {
    812     int x, y;
    813     cin >> x >> y;
    814     G[x].push_back(y);
    815     G[y].push_back(x);
    816   }
    817   dfs(1, -1);
    818   for (int i = 1; i <= l; i++) {
    819     rmq[i][0] = {st[eu[i]], eu[i]};
    820   }
    821   init();
    822   for (int i = 1; i <= n; i++) {
    823     low[i] = i;
    824     ok[i] = 0;
    825   }
    826   for (int i = 1; i <= m; i++) {
    827     int x, y;
    828     cin >> x >> y;
    829     ed[i] = {x, y};
    830     int u = LCA(x, y);
    831     if (h[low[x]] > h[u]) {
    832       low[x] = u;
    833     }
    834     if (h[low[y]] > h[u]) {
    835       low[y] = u;
    836     }
    837   }
    838   int need = 0;
    839   for (int i = 2; i <= n; i++) {
    840     if (low[i] != 1 && G[i].size() == 1) {
    841       if (need == 0 || h[low[need]] < h[low[i]]) {
    842         need = i;
    843       }
    844     }
    845   }
    846   if (need == 0) {
    847     cout << "YES\n";
    848     return;
    849   }
    850   for (int i = 1; i <= m; i++) {
    851     int u = LCA(ed[i].first, ed[i].second);
    852     if (G[ed[i].first].size() == 1 && check(ed[i].second, u, low[need])) {
    853       ok[ed[i].first] = 1;
    854     }
    855     if (G[ed[i].second].size() == 1 && check(ed[i].first, u, low[need])) {
    856       ok[ed[i].second] = 1;
    857     }
    858   }
    859   for (int i = 1; i <= n; i++) {
    860     if (G[i].size() == 1) {
    861       if (st[low[need]] <= st[i] && st[i] <= out[low[need]]) {
    862         continue;
    863       }
    864       if (ok[i] == 0) {
    865         cout << "NO\n";
    866         cout << need << " " << i << "\n";
    867         return;
    868       }
    869     }
    870   }
    871   cout << "YES\n";
    872   return;
    873 }
    874 signed main() {
    875   cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
    876   int t;
    877   cin >> t;
    878   while (t--) solve();
    879   return 0;
    880 }
    881 ```
    882 
    883 **sorry gamegame**
    884 
    885 ![ ](/predownloaded/5e/ed/5eed5b4fe0d60fa25daf24edb1d4cc7ec1dbab73.png)
    886 
    887 ## [1827F - Copium Permutation](/contest/1827/problem/F "Codeforces Round 873 (Div. 1)")
    888 
    889 Idea: [lanhf](/profile/lanhf "Master lanhf")   
    890  Preparation: [lanhf](/profile/lanhf "Master lanhf")
    891 
    892 **Solution**
    893 
    894 ### Solve the problem for fixed $k$
    895 
    896 Call the last $n-k$ elements as special numbers.
    897 
    898 **Observation**: In optimal rearrangement, every maximal segment of special numbers will be placed on consecutive positions in either ascending order or descending order. For simplicity, from now on we will call maximal segment of special number as maximal segment.
    899 
    900 For example, take a permutation $p=[7, 5, 8, 1, 4, 2, 6, 3]$ and $k=2$, the maximal segments are $[1, 4]$, $[6, 6]$ and $[8, 8]$.
    901 
    902 We divide the set of copium subarrays into three parts, one for those lie entirely on prefix $p[1..k]$, one for those lie entirely on suffix $p[k+1..n]$, and one for the rest. The number of subarrays in the first part can be calculated with the algorithm used in [526F - Pudding Monsters](/contest/526/problem/F "ZeptoLab Code Rush 2015"). The number of subarrays in the second part can be easily deduced from above observation.
    903 
    904 Define an array $good=[good_1,good_2,\ldots,good_m]$ such that for each $i$: $good_i \lt good_{i+1}$ and subarray $p[good_i..k]$ contains consecutive nonspecial numbers.
    905 
    906 For example, take a permutation $p=[1, 5, 4,3,7,8,9,2,10,6]$ and $k=5$, then $good=[1, 4, 5]$.
    907 
    908 We will process $good$ array from right to left while adding special numbers from left to right. Let us consider $good_i$, first add all special numbers which are missing from subarray $[good_i, k]$ at the end of current permutation. If $[good_i, k]$ is not already copium, we increase our answer by one. Denote $mn_i$ and $mx_i$ as the minimum and maximum number in subarray $[good_i, k]$. Loot at two maximal segments, one contains $mn_i-1$ and one contains $mx_i+1$. We can place them here to increase the answer.
    909 
    910 For example, let $n=10$, $k=5$, $good_i=3$ and the current permutation $p=[1, 10, 4, 5, 7, 6]$. The two maximal segments are $[2, 3]$ and $[8, 9]$. We can place them like $[1, 10, 4, 5, 7, 6, 8, 9, 3, 2]$ to increase the answer by 4. Furthermore, we can see that three good positions $3$, $4$ and $5$ benefit from maximal segment $[8, 9]$. In general, consider consecutive good positions $good_i, good_{i+1},\ldots, good_j$ satisfying $mx_i=mx_{i+1}=\ldots=mx_j$, all of them can benefit from the same maximal segment if for all $i\le x \lt j$, subarray $[good_x..good_{x+1}-1]$ is copium $(*)$.
    911 
    912 There is a similar condition when we consider consecutive good positions having the same $mn$. So the algorithm goes like this: For each value of $mn$ and $mx$, find the longest segment of good positions satisfying condition $(*)$, then multiply with the length of corresponding maximal segment and add to the answer.
    913 
    914 ### Solve for each $k$
    915 
    916 We will calculate the answer for each $k$ from $0$ to $n$ in this order. We will store the longest segment for each prefix of $mn$-equivalent and $mx$-equivalent positions. Note that when going from $k-1$ to $k$, only a suffix of $good$ will no longer be good, so we can manually delete them one by one from right to left, then add $k$. There will be at most $2$ good positions we need to consider. The first one, of course, is $k$. If $p_{k-1} \lt p_k$ or $p_{k-1} \gt p_k$, let $j$ be the last position satisfying $p_j \gt p_k$ or $p_j \lt p_k$, the second one is the first good position after $j$ and it satisfies a property: It must be the last position in the $mn$-equivalent or $mx$-equivalent positions. The proof is left as an exercise. Therefore, updating this position will not affect the positions behind it. The overall complexity is $\mathcal{O}(n\log n)$.
    917 
    918 **Implementation**
    919 
    920 ```
    921 #include <bits/stdc++.h>
    922 
    923 using namespace std;
    924 
    925 using ll = long long;
    926 
    927 const int N = 200005;
    928 const int LOG = 18;
    929 
    930 int n, a[N], pos[N];
    931 int lef[N], rig[N];
    932 
    933 vector<int> st_max, st_min;
    934 
    935 void connect(int x, int y) {
    936   rig[x] = y; lef[y] = x;
    937 }
    938 
    939 struct range_min {
    940   vector<int> spt[LOG];
    941   
    942   void build() {
    943     for (int k = 0; k < LOG; k++)
    944       spt[k].resize(n + 1);
    945     for (int i = 1; i <= n; i++)
    946       spt[0][i] = pos[i];
    947     for (int k = 1; k < LOG; k++)
    948       for (int i = 1; i + (1 << k) <= n + 1; i++) {
    949         spt[k][i] = min(spt[k - 1][i],
    950         spt[k - 1][i + (1 << (k - 1))]);
    951       }
    952   }
    953   
    954   int get_min_pos(int l, int r) {
    955     int k = __lg(r - l + 1);
    956     return min(spt[k][l], spt[k][r - (1 << k) + 1]);
    957   }
    958 } rmq;
    959 
    960 int get_min(int i) {
    961   return a[*lower_bound(st_min.begin(), st_min.end(), i)];
    962 }
    963 
    964 int get_max(int i) {
    965   return a[*lower_bound(st_max.begin(), st_max.end(), i)];
    966 }
    967 
    968 struct segtree1 {
    969 #define il i * 2
    970 #define ir i * 2 + 1
    971   struct node {
    972     int val, cnt, tag;
    973   };
    974   
    975   node tree[N * 4];
    976   
    977   void build(int i, int l, int r) {
    978     tree[i] = {l, 1, 0};
    979     if (l < r) {
    980       int m = (l + r) / 2;
    981       build(il, l, m);
    982       build(ir, m + 1, r);
    983     }
    984   }
    985   
    986   void add(int i, int l, int r, int x, int y, int v) {  
    987     if (l >= x && r <= y) {
    988       tree[i].val += v; tree[i].tag += v; return;
    989     }
    990 
    991     int m = (l + r) / 2;
    992     if (m >= x) add(il, l, m, x, y, v);
    993     if (m < y) add(ir, m + 1, r, x, y, v);
    994   
    995     tree[i].val = tree[il].val;
    996     tree[i].cnt = tree[il].cnt;
    997 
    998     if (tree[i].val > tree[ir].val) {
    999       tree[i].val = tree[ir].val;
   1000       tree[i].cnt = tree[ir].cnt;
   1001     } else if (tree[i].val == tree[ir].val)
   1002       tree[i].cnt += tree[ir].cnt;
   1003 
   1004     tree[i].val += tree[i].tag;
   1005   }
   1006 #undef il
   1007 #undef ir
   1008 } seg1;
   1009 
   1010 struct copium {
   1011   int curr, maxx, type;
   1012   
   1013   copium() {}
   1014   
   1015   copium(int curr, int maxx, int type):
   1016   curr(curr), maxx(max(maxx, curr)), type(type) {}
   1017 };
   1018 
   1019 copium lmin[N], lmax[N];
   1020 ll prefix, middle, suffix;
   1021 
   1022 /// cancer
   1023 void calc(int i, int j, bool recalc) {
   1024   int imin = get_min(i), imax = get_max(i);
   1025   int jmin = get_min(j), jmax = get_max(j);
   1026   int type;
   1027   if (recalc) {
   1028     middle -= 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1);
   1029     middle -= 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1);
   1030   }
   1031   
   1032   if (imax == jmax) {
   1033     if (!recalc)
   1034       middle -= 1ll * lmax[i].maxx * (rig[imax] - imax - 1);
   1035       
   1036     if (jmin - imin == j - i) type = 0;
   1037     else if (imin + j - i == lef[jmin] + 1) type = 1;
   1038     else type = 2;
   1039     
   1040     if (type == 2) lmax[j] = copium(1, lmax[i].maxx, type);
   1041     else if (lmax[i].type == 0)
   1042       lmax[j] = copium(lmax[i].curr + 1, lmax[i].maxx, type);
   1043     else lmax[j] = copium(2, lmax[i].maxx, type);
   1044     
   1045   } else lmax[j] = {1, 1, 3};
   1046   if (imin == jmin) {
   1047     if (!recalc)
   1048       middle -= 1ll * lmin[i].maxx * (imin - lef[imin] - 1);
   1049       
   1050     if (imax - jmax == j - i) type = 0;
   1051     else if (imax + i - j == rig[jmax] - 1) type = 1;
   1052     else type = 2;
   1053     
   1054     if (type == 2) lmin[j] = copium(1, lmin[i].maxx, type);
   1055     else if (lmin[i].type == 0)
   1056       lmin[j] = copium(lmin[i].curr + 1, lmin[i].maxx, type);
   1057     else lmin[j] = copium(2, lmin[i].maxx, type);
   1058     
   1059   } else lmin[j] = {1, 1, 3};
   1060   
   1061   middle += 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1);
   1062   middle += 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1);
   1063 }
   1064 
   1065 int main() {
   1066   cin.tie(0)->sync_with_stdio(0);
   1067   int t; cin >> t;
   1068   while (t--) {
   1069     cin >> n;
   1070     for (int i = 1; i <= n; i++) {
   1071       cin >> a[i]; pos[a[i]] = i;
   1072       lef[i] = rig[i] = 0;
   1073     }
   1074     
   1075     st_min.assign(1, 0);
   1076     st_max.assign(1, 0);
   1077     
   1078     set<int> sorted;
   1079     sorted.insert(0);
   1080     sorted.insert(n + 1);
   1081     
   1082     prefix = 0;
   1083     suffix = 1ll * n * (n + 1) / 2;
   1084     middle = 0;
   1085     
   1086     // k = 0
   1087     cout << suffix << ' ';
   1088     
   1089     lef[n] = 0; rig[0] = n;
   1090     
   1091     seg1.build(1, 1, n); rmq.build();
   1092     
   1093     vector<int> good;
   1094     
   1095     for (int i = 1; i <= n; i++) {
   1096       
   1097       while (good.size()) { 
   1098         int j = good.back();
   1099         int jmin = get_min(j), jmax = get_max(j);
   1100         
   1101         if (rmq.get_min_pos(min(jmin, a[i]), max(jmax, a[i])) < j) {
   1102           middle -= 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1);
   1103           middle -= 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1);
   1104           good.pop_back();
   1105           if (good.size()) {
   1106             if (lmax[j].type < 3)
   1107               middle += 1ll * lmax[good.back()].maxx * (rig[jmax] - jmax - 1);
   1108             if (lmin[j].type < 3)
   1109               middle += 1ll * lmin[good.back()].maxx * (jmin - lef[jmin] - 1);
   1110           }
   1111         } else break;
   1112       }
   1113       
   1114       if (good.size()) {
   1115         int j = good.back();
   1116         int jmin = get_min(j), jmax = get_max(j);
   1117         middle -= 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1);
   1118         middle -= 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1); 
   1119       }
   1120       
   1121       auto it = sorted.upper_bound(a[i]);
   1122       suffix -= 1ll * (*it - a[i]) * (a[i] - *prev(it));
   1123       connect(*prev(it), a[i]); connect(a[i], *it);
   1124       sorted.insert(a[i]);
   1125       
   1126       while (st_max.size() > 1 && a[st_max.back()] < a[i]) {
   1127         seg1.add(1, 1, n, st_max[st_max.size() - 2] + 1,
   1128         st_max.back(), a[i] - a[st_max.back()]);
   1129         st_max.pop_back();
   1130       }
   1131       
   1132       while (st_min.size() > 1 && a[st_min.back()] > a[i]) {
   1133         seg1.add(1, 1, n, st_min[st_min.size() - 2] + 1,
   1134         st_min.back(), a[st_min.back()] - a[i]);
   1135         st_min.pop_back(); 
   1136       }
   1137       
   1138       st_max.push_back(i); st_min.push_back(i);
   1139       
   1140       if (good.size()) {
   1141         int j = good.back();
   1142         int jmin = get_min(j), jmax = get_max(j);
   1143         middle += 1ll * lmax[j].maxx * (rig[jmax] - jmax - 1);
   1144         middle += 1ll * lmin[j].maxx * (jmin - lef[jmin] - 1); 
   1145         calc(j, i, 0);
   1146       } else {
   1147         lmax[i] = lmin[i] = {1, 1, 3};
   1148         middle += rig[a[i]] - lef[a[i]] - 2;
   1149       }
   1150 
   1151       good.push_back(i);
   1152       if (st_min.size() >= 2) {
   1153         int k = upper_bound(good.begin(), good.end(),
   1154         st_min[st_min.size() - 2]) - good.begin();
   1155         if (k > 0 && k < good.size())
   1156           calc(good[k - 1], good[k], 1);
   1157       }
   1158       if (st_max.size() >= 2) {
   1159         int k = upper_bound(good.begin(), good.end(),
   1160         st_max[st_max.size() - 2]) - good.begin();
   1161         if (k > 0 && k < good.size())
   1162           calc(good[k - 1], good[k], 1);
   1163       }
   1164       
   1165       cout << prefix + good.size() + middle + suffix << ' ';
   1166       
   1167       prefix += seg1.tree[1].cnt; 
   1168     }
   1169     cout << '\n';
   1170   }
   1171 }
   1172 ```