codeforces-scrape

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

2211.md (48737B)


      1 Source: https://codeforces.com/blog/entry/152448
      2 
      3 **Rating Predictions**
      4 
      5 | Predictor | A | B | C | D | E | F | G | H |
      6 | --- | --- | --- | --- | --- | --- | --- | --- | --- |
      7 | [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED") | 800 | 1300 | (1400-2000) | 1700 | 2100 | 2400 | 2600 | 3500 |
      8 | [nifeshe](/profile/nifeshe "Grandmaster nifeshe") | 800 | 1400 | (1400-1900) | 1800 | 2200 | 2600 | 3000 | 3500 |
      9 | [dinohaur](/profile/dinohaur "Grandmaster dinohaur") | 800 | 1200 | (1400-1700) | 2100 | 2300 | 2600 | 2900 | 3300 |
     10 | [_istil](/profile/_istil "Grandmaster _istil") | 800 | 1200 | (1300-1800) | 1900 | 2300 | 2500 | 2800 | 3300 |
     11 | [Dragos](/profile/Dragos "Grandmaster Dragos") | 800 | 1400 | (1400-1900) | 1800 | 2100 | 2400 | 2800 | 3500 |
     12 | [Argentum47](/profile/Argentum47 "Expert Argentum47") | 800 | 1300 | (1400-2000) | 1900 | 2200 | 2500 | ? | ? |
     13 | [simplelife](/profile/simplelife "Expert simplelife") | 800 | 1200 | (1200-1800) | 1600 | 2000 | 2500 | 6700 | 6700 |
     14 | [AksLolCoding](/profile/AksLolCoding "Master AksLolCoding") | 800 | 1000 | (1100-1800) | 1600 | 1900 | 2400 | ? | ? |
     15 | [nik_exists](/profile/nik_exists "Specialist nik_exists") | 800 | 1100 | (1100-?) | 1800 | 2000 | ? | ? | ? |
     16 
     17 #### [2211A - Antimedian Deletion](/contest/2211/problem/A)
     18 
     19 Problem Credits: [nifeshe](/profile/nifeshe "Grandmaster nifeshe"), [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED")
     20 
     21 **Hint 1**
     22 
     23 You are allowed to delete two elements in any valid subarray, but you only need to keep one.
     24 
     25 **Solution**
     26 
     27 A lower bound for the answer for each element is $2$ (or $1$ if $n=1$), as if the array size is $2$ or less, then no operations are even possible.
     28 
     29 This bound is achievable for any element in any permutation. We can choose our subarray of size $3$ arbitrarily. Suppose $x$ is the value we want to keep in the array. If $x$ is the minimum element, we can delete the largest element. Otherwise, we can delete the smallest element.
     30 
     31 **Code**
     32 
     33 ```
     34 def solve():
     35     n = int(input())
     36     a = list(map(int, input().split()))
     37     if n==1:
     38         print("1\n")
     39     else:
     40         for i in range(n):
     41             print("2 ")
     42         print("\n")
     43 
     44 t = int(input())
     45 for i in range(t):
     46     solve()
     47 ```
     48 
     49 **Rate The Problem!**
     50 
     51 * Good Problem
     52 * Okay Problem
     53 * Bad Problem
     54 * Didn't Solve
     55 
     56 #### [2211B - Mickey Mouse Constructive](/contest/2211/problem/B)
     57 
     58 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED")
     59 
     60 **Hint 1**
     61 
     62 Since the array consists only of $1$ and $-1$, the growth rate of the cumulative sum must be $1$ or $-1$. In other words, you can't skip a number. What can you say about a lower bound of the answer from this?
     63 
     64 **Solution**
     65 
     66 For an array $a$, denote $p_i=a_1+a_2+\ldots+a_i$. Define $p_0=0$. We can see that the sum of the subarray from $l$ to $r$ is $p_r-p_{l-1}$.
     67 
     68 Let's lower bound our answer. First, suppose that $x \ne y$. Without loss of generality that $x \ge y$ (so $p_{x+y} \gt 0$). Fix $d$ to be a divisor of $|x-y|$. Since our array contains only $1$ and $-1$ (and thus $p_i$ changes by only $1$ or $-1$ every time), and that $p_0=0$ while $p_{x+y}=x-y$, there must exist an index $i$ where $p_i=d$ (this is the discrete version of the Intermediate Value Theorem). Let this index be $i_1$. By the same logic, there must be an index $i_2$ between $i_1$ and $x+y$ such that $p_{i_2}=2\cdot d$. Continuing this process, we can see that for every divisor $d$ of $x-y$, there must exist at least one valid partition with all subarrays having equal sum. Therefore, a lower bound for the answer is the number of divisors of $x-y$. The case of $x \le y$ is analogous.
     69 
     70 Then, can we reach this lower bound? It turns out the construction $[1, 1, \ldots, 1, -1, -1, \ldots, -1]$ reaches this lower bound. For a fixed divisor $d$, there is only one valid index $i$ each time, except for $x-y$, of which there are two indices. However, since the last subarray in the partition must reach $n$, this doesn't matter to us.
     71 
     72 This solves the case for $x \ne y$. But what about $x=y$? Our above analysis of Intermediate Value Theorem breaks, as the start and final value are both $0$. The answer is at least $1$, since the full array is valid. We can reach this lower bound using the same construction above (as there does not exist any indices other than $0$ and $x+y$ with $p_i=0$).
     73 
     74 **Code**
     75 
     76 ```
     77 import sys
     78 input = sys.stdin.readline
     79 
     80 t = int(input())
     81 for _ in range(t):
     82     x, y = map(int, input().split())
     83     s = x - y
     84     
     85     a = []
     86     for _ in range(x):
     87         a.append(1)
     88     for _ in range(y):
     89         a.append(-1)
     90     
     91     ans = 0
     92     for i in range(1, abs(s) + 1):
     93         if s % i == 0:
     94             ans += 1
     95     
     96     if s == 0:
     97         ans = 1
     98     
     99     print(ans)
    100     print(*a)
    101 ```
    102 
    103 **Rate The Problem!**
    104 
    105 * Good Problem
    106 * Okay Problem
    107 * Bad Problem
    108 * Didn't Solve
    109 
    110 #### [2211C1 - Equal Multisets (Easy Version)](/contest/2211/problem/C1)
    111 
    112 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED")
    113 
    114 Special thanks to [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") for suggesting this subtask.
    115 
    116 **Hint 1**
    117 
    118 Consider the cases of $k=n$ and $k=n-1$. What do you notice?
    119 
    120 **Solution**
    121 
    122 Our first observation is that $b$ has to be a permutation (after replacing all $-1$'s). This is because since $a$ is a permutation, and each element appears in at least one valid subarray, if $b$ is not a permutation then at least one element does not exist in $b$, meaning that the answer must be no.
    123 
    124 It may help to visualize this problem using some examples first:
    125 
    126 * If $k=n$, then the answer is only YES if there are no repeat elements in $b$.
    127 * What if $k=n-1$? Now, the requirements are more strict. If you have $b_1 \ne a_1$, $a_1$ would need to appear somewhere later. But then this means that in the subarray $[2,n-1]$, $a_1$ appears in the subarray in $b$ but not in $a$. Similarly, $a_n$ must be the same as $b_n$. We can see that the remaining $n-2$ elements are allowed to be any rearrangement of the middle $n-2$ elements in $a$.
    128 
    129 Continuing on to $k=n-2$, using the same logic, we see that the first and last $2$ elements of $a$ must match with the first and last $2$ elements of $b$, with the middle $n-4$ numbers being allowed to be anything.
    130 
    131 We now see that this forms a pattern: the first $n-k$ elements and the last $n-k$ elements in $a$ and $b$ must match, and the middle $2k-n$ elements must be rearrangements of each other. If $2k \lt n$, then we must have $a=b$ naturally. Let's now show that it works.
    132 
    133 Consider the union of all size $k$ intervals: starting from $[1,k]$, then $[2,k+1]$, and so on. The interval that is inside all of these intervals is the union of $[1,k]$ and $[n-k+1,n]$ (intuitively, we can see this is true because $[1,k]$ is the leftmost interval, and $[n-k+1,n]$ is the rightmost one. Therefore, any point inside both of these intervals must be shared among all length $k$ intervals). The length of the intersection is $\max(2k-n,0)$. Any point not in this common interval must be the same in $a$ and $b$, as there exists an interval that doesn't contain it.
    134 
    135 **Rate The Problem!**
    136 
    137 * Good Problem
    138 * Okay Problem
    139 * Bad Problem
    140 * Didn't Solve
    141 
    142 #### [2211C2 - Equal Multisets (Hard Version)](/contest/2211/problem/C2)
    143 
    144 Problem credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED")
    145 
    146 **Hint 1**
    147 
    148 Consider the transition from the interval $[l,r]$ to $[l+1,r+1]$. What do you "gain"? What do you "lose"?
    149 
    150 **Solution**
    151 
    152 We need to take a different approach from problem C1. Consider transferring from the interval $[l,r]$ to $[l+1,r+1]$. In the multiset of $b$, we need to "lose" the element $a_l$ and "gain" the element $a_r$. At first glance, this seems very restrictive: is there even any cases where $a_l \ne b_l, a_r \ne b_r$ and this can still work out?
    153 
    154 In fact, the only other case that doesn't break the condition is if $a_l=a_r$ and $b_l=b_r$. Otherwise, you would need $b_r$ to "recover" the lost element from $a_r$ and also whatever element was lost at $b_l$ at the same time, which is impossible (if $a_l=a_r$, then $a_r$ "recovered" the element $a_l$ in the multiset).
    155 
    156 This motivates us to split the arrays $a$ and $b$ into $k$ subsequences, depending on their indices modulo $k$. In each subsequence, if all elements of $a$ are the same, then all elements of $b$ must be the same. Otherwise, we must have $a_i=b_i$ for each index in the subsequence.
    157 
    158 There is one more requirement: we need to ensure that the first $k$ elements of $a$ and $b$ can match. Our transition conditions ensure that if $[l,r]$ works, then $[l+1,r+1]$ also does. But we would need the "base" interval $[1,k]$ to work first (this process is much like the process of induction). Once we fill in values of $b$ that is required in our previous step, all we need to do is ensure that no number in the first $k$ indices appears more often in $b$ than $a$.
    159 
    160 **Code**
    161 
    162 ```
    163 #include <bits/stdc++.h>
    164 using namespace std;
    165 #define int long long 
    166 
    167 void solve() {
    168 	int n, k; cin >> n >> k;
    169 	vector<int> a(n), b(n);
    170 	for (auto &x : a) cin >> x;
    171 	for (auto &x : b) cin >> x;
    172 	
    173 	vector<bool> vis(n);
    174 	vector<int> pos(k);
    175 	map<int, int> cnt;
    176 	for (int i = 0; i < k; i++) {
    177 		pos[i] = a[i];
    178 		for (int j = i + k; j < n; j += k) {
    179 			if (pos[i] != a[j]) pos[i] = -1;
    180 		}
    181 		if (pos[i] != -1) cnt[pos[i]]++;
    182 		
    183 		if (pos[i] == -1) {
    184 			for (int j = i; j < n; j += k) {
    185 				if (b[j] != -1 && b[j] != a[j]) {
    186 					cout << "NO" << "\n";
    187 					return;
    188 				}
    189 			}
    190 		}
    191 	}
    192 	
    193 	map<int, int> cnt2;
    194 	vector<int> ans(k);
    195 	for (int i = 0; i < k; i++) {
    196 	if (pos[i] != -1) {
    197 		set<int> d;
    198 		for (int j = i; j < n; j += k)
    199 			d.insert(b[j]);
    200 		d.erase(-1);
    201 		
    202 		if (d.size() >= 2) {
    203 			for (int j = i; j < n; j += k)
    204 				if (b[j] != -1 && b[j] != a[j]) {
    205 					cout << "NO" << "\n";
    206 					return;
    207 				}
    208 		}
    209 		if (d.size() == 1)
    210 			cnt2[*d.begin()]++;
    211 	}
    212 	}
    213 	
    214 	for (auto [k, x] : cnt2) {
    215 		if (x > cnt[k]) {
    216 			cout << "NO" << "\n";
    217 			return;
    218 		}
    219 	}
    220 	
    221 	cout << "YES" << "\n";
    222 	
    223 }
    224 
    225 signed main() {
    226 	int T;
    227 	cin >> T;
    228 	while (T--)
    229 		solve();
    230 }
    231 ```
    232 
    233 **Rate The Problem!**
    234 
    235 * Good Problem
    236 * Okay Problem
    237 * Bad Problem
    238 * Didn't Solve
    239 
    240 #### [2211D - AND-array](/contest/2211/problem/D)
    241 
    242 Problem credits: [nifeshe](/profile/nifeshe "Grandmaster nifeshe")
    243 
    244 **Hint 1**
    245 
    246 How is the checker implemented? In other words, given $a$ find $f(a)$.
    247 
    248 **Hint 2**
    249 
    250 Let $\text{cnt}_l$ be the number of $i$ such that $a_i$ has the bit $l$ set. $f(a)$ only depends on the array $\text{cnt}$.
    251 
    252 **Hint 3**
    253 
    254 $f(a)_k = \sum\limits_{l = 0}^{28} 2^l \cdot \binom{\text{cnt}_l}{k}$.
    255 
    256 **Hint 4**
    257 
    258 Look at $b_n$. This value tells us all the bits $l$ that have $\text{cnt}_l = n$.
    259 
    260 **Hint 5**
    261 
    262 We can remove all the bits in $b_n$: for all set bits in $b_n$ and $1 \le k \lt n$ set $b_k = b_k - \binom{n}{k} \cdot 2^l$. After that no bit occurs $n$ times in $a$, so set $n = n - 1$.
    263 
    264 **Hint 6**
    265 
    266 Since $a$ is guaranteed to exist, each bit will be removed at most once, so the time complexity is $O(n \log A)$.
    267 
    268 **Solution**
    269 
    270 Given $a$, how can we find $f(a)$? Consider each bit separately: assume $a_i$ is either $0$ or $1$. If there are $m$ ones in $a$, then $f(a)_k = \binom{m}{k}$ — the number of ways to pick $k$ ones from $m$, since every index in the subsequence has to be a $1$.
    271 
    272 This can be generalized to all $a$: let $\text{cnt}_l$ be the number of $i$ such that $a_i$ has the bit $l$ set. $f(a)$ only depends on the array $\text{cnt}$, and $f(a)_k = \sum\limits_{l = 0}^{28} 2^l \cdot \binom{\text{cnt}_l}{k}$.
    273 
    274 Now we need to restore $a$ from $f(a)$. Look at $b_n$. This value tells us all the bits $l$ that have $\text{cnt}_l = n$.
    275 
    276 We can remove all the bits in $b_n$: for all set bits in $b_n$ and $1 \le k \lt n$ set $b_k = b_k - \binom{n}{k} \cdot 2^l$.
    277 
    278 After that no bit occurs $n$ times, and since $f(a)$ only depends on the array $\text{cnt}$, we can assume that $n = n - 1$ and repeat the same procedure. This way we can uniquely determine the array $\text{cnt}$.
    279 
    280 The only thing left is the actually find any feasible $a$. We can do that the following way: for all bits $l$ and $i$ in $[1, \text{cnt}_l]$ set the $l$-th bit in $a_i$. This $a$ corresponds to the found array $\text{cnt}$.
    281 
    282 The only concern is the time complexity. However, since the answer is guaranteed to exist we will delete each bit at most once, so the final solution is $O(n \log A)$.
    283 
    284 **Code**
    285 
    286 ```
    287 #include <bits/stdc++.h>
    288 
    289 using namespace std;
    290 
    291 const int mod = 1e9 + 7;
    292 const int MAX = 2e5 + 5;
    293 const int LG = 29;
    294 
    295 int binpow(int x, int n) {
    296     int ans = 1;
    297     while(n) {
    298         if(n & 1) ans = (long long) ans * x % mod;
    299         n >>= 1;
    300         x = (long long) x * x % mod;
    301     }
    302     return ans;
    303 }
    304 
    305 int fact[MAX], inv[MAX];
    306 
    307 int C(int n, int k) {
    308     if(n < k || k < 0) return 0;
    309     return (long long) fact[n] * inv[k] % mod * inv[n - k] % mod;
    310 }
    311 
    312 void solve() {
    313     int n;
    314     cin >> n;
    315     vector<int> b(n);
    316     for(auto &i : b) {
    317         cin >> i;
    318     }
    319     
    320     vector<int> cnt(LG);
    321     for(int i = n - 1; ~i; i--) {
    322         for(int l = 0; l < LG; l++) {
    323             if(b[i] >> l & 1) {
    324                 cnt[l] = i + 1;
    325                 
    326                 for(int j = 0; j <= i; j++) {
    327                     int subtract = (long long) C(i + 1, j + 1) * (1 << l) % mod;
    328                     b[j] -= subtract;
    329                     if(b[j] < 0) b[j] += mod;
    330                 }
    331             }
    332         }
    333     }
    334     
    335     vector<int> a(n);
    336     for(int l = 0; l < LG; l++) {
    337         for(int i = 0; i < cnt[l]; i++) {
    338             a[i] |= 1 << l;
    339         }
    340     }
    341     for(auto i : a) cout << i << " "; cout << '\n';
    342 }
    343 
    344 signed main() {
    345     fact[0] = 1; for(int i = 1; i < MAX; i++) fact[i] = (long long) fact[i - 1] * i % mod;
    346     inv[MAX - 1] = binpow(fact[MAX - 1], mod - 2);
    347     for(int i = MAX - 1; i; i--) inv[i - 1] = (long long) inv[i] * i % mod; assert(inv[0] == 1);
    348     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    349     int tests = 1;
    350     cin >> tests;
    351     for(int test = 0; test < tests; test++) {
    352         solve();
    353     }
    354 }
    355 ```
    356 
    357 **Rate The Problem!**
    358 
    359 * Good Problem
    360 * Okay Problem
    361 * Bad Problem
    362 * Didn't Solve
    363 
    364 #### [2211E - Minimum Path Cover](/contest/2211/problem/E)
    365 
    366 Problem credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED")
    367 
    368 **Hint 1**
    369 
    370 The reason why most naive DP approaches fail is because you cannot factorize $2\cdot 10^5$ numbers of scale $10^{18}$ fast. How do you avoid this?
    371 
    372 **Hint 2**
    373 
    374 The solution to the problem does not change if "each node is covered by exactly one path" was replaced by "each node is covered by at least one path"
    375 
    376 **Solution**
    377 
    378 Read the hints.
    379 
    380 The most naive approach is something like $dp(node,x)$ to the minimum number of paths used to cover the subtree of $node$, such that the path from $node$ has GCD $x$. With potentially up to $d(a_{node})$ different states of DP at each node (where $d(x)$ is the number of divisors of $x$), this will easily get the Time Limit Exceeded verdict.
    381 
    382 However, we take advantage of the fact that in a tree, each node can have only one parent. In other words, there can only be one path going upwards starting at each node. For simplicity, assume that each path must end as a prime number (if the path instead ends with something like $6$, it is counted as both ending in $2$ and $3$). We can then perform a DP like $dp(node,x)$ being the smallest number of paths to cover the subtree of $node$, assuming that the path going up from $node$ is $x$ (where $x$ must be prime).
    383 
    384 Unfortunately, finding the prime factors of the numbers is still impossible. However, what if we don't need to? Consider a greedy strategy where you extend every path from the children of node $x$ upwards if the GCD does not become $1$. (because of our analysis above, the solution to the problem does not change if "each node is covered by exactly one path" is replaced by "each node is covered by at least one path"). While we cannot store all possible values of a path, we *can* store the LCM of all such paths. It's not hard to show that storing the LCM is functionally the same as storing all possible values of a path.
    385 
    386 So the solution is as follows: let $dp(x)$ represent the minimum number of paths to cover the subtree of $x$, and let $val(x)$ be the LCM of all paths that can pass through $x$. When trying to find the answers for $x$, we first set $val(x)=1$. For each child $c$ of $x$, set $val(x)=\text{LCM}(val(x), val(c))$. Set $dp(x)$ to be the sum of $dp(c)$, and add $1$ if $val(x)=1$ (as well as updating $val(x)=a_x$). This solution is very simple and runs in $O(n \log A)$
    387 
    388 Since the values of $a_i$ are large, we must calculate LCM as $a/\text{GCD}(a,b)\cdot b$ instead of $(a\cdot b)/\text{GCD}(a,b)$. However, note that the calculations will never overflow $64$-bit integers, as they are upper bounded by $a_i$.
    389 
    390 As an alternative to maintaining the LCM, you can actually maintain the set of possible GCD values, but ensure that they are pairwise coprime. This solution is expected to run in $O(n \log ^2{A})$
    391 
    392 **Rate The Problem!**
    393 
    394 * Good Problem
    395 * Okay Problem
    396 * Bad Problem
    397 * Didn't Solve
    398 
    399 **Code**
    400 
    401 ```
    402 #include <bits/stdc++.h>
    403 using namespace std;
    404 #define rep(i,a,n) for (int i=(a);i<(n);i++)
    405 #define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
    406 #define pb push_back
    407 #define eb emplace_back
    408 #define mp make_pair
    409 #define all(x) (x).begin(),(x).end()
    410 #define fi first
    411 #define se second
    412 #define SZ(x) ((int)(x).size())
    413 typedef vector<int> VI;
    414 typedef basic_string<int> BI;
    415 typedef long long ll;
    416 typedef pair<int,int> PII;
    417 typedef double db;
    418 mt19937 mrand(random_device{}()); 
    419 const ll mod=676767677;
    420 int rnd(int x) { return mrand() % x;}
    421 ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    422 // head
    423 
    424 const int N=201000;
    425 int n,dp[N];
    426 ll d[N],v[N];
    427 ll a[N];
    428 void solve() {
    429 	scanf("%d",&n);
    430 	per(i,1,n+1) {
    431 		int k;
    432 		scanf("%lld",&a[i]);
    433 		scanf("%d",&k);
    434 		VI s;
    435 		dp[i]=0;
    436 		bool val=0;
    437 		rep(j,0,k) {
    438 			int x;
    439 			scanf("%d",&x);
    440 			s.pb(x);
    441 			dp[i]+=dp[x];
    442 			d[x]=gcd(v[x],a[i]);
    443 			val|=d[x]>1;
    444 		}
    445 		if (val) {
    446 			ll z=1;
    447 			for (auto x:s) if (d[x]>1) z=lcm(z,d[x]);
    448 			v[i]=z;
    449 		} else {
    450 			dp[i]+=1;
    451 			v[i]=a[i];
    452 		}
    453 		printf("%d\n",dp[i]);
    454 		fflush(stdout);
    455 	}
    456 }
    457 
    458 int _;
    459 int main() {
    460 	for (scanf("%d",&_);_;_--) {
    461 		solve();
    462 	}
    463 }
    464 ```
    465 
    466 #### [2211F - Learning Binary Search](/contest/2211/problem/F)
    467 
    468 Problem credits: [Proof_by_QED](/profile/Proof_by_QED "International Master Proof_by_QED")
    469 
    470 Unfortunately, it seems like there are a lot of cheaters on this problem. We will do the best to clear them out, but keep in mind this is out of our control.
    471 
    472 **Hint 1**
    473 
    474 Consider what the contribution of a number is.
    475 
    476 **Hint 2**
    477 
    478 Come up with $O(nm)$ or $O(n^2)$ solution first. There is an identity that can simplify.
    479 
    480 **Solution 1**
    481 
    482 Simulate the binary search so we get the weight of each index. Now, we want to partition it into $m$ segments (potentially empty) where the weight of each segment is the minimum number that it covers.
    483 
    484 Suppose we fix the number $x$, as well as the interval that it covers $[l,r]$. This means that we need to cover the interval $[1,l-1]$ with the numbers $1$ through $x-1$, and the interval $[r+1,n]$ with the numbers $x+1$ through $m$. Denote $y=m-x$. Then, using stars and bars, we get the number of ways to fill other numbers as:
    485 
    486 $\binom{l+x-3}{x-2}\binom{y+n-r-1}{y-1}$
    487 
    488 This sum is to be taken over all $x$ from $2$ to $m-1$ (ignore the edge cases of $x=1$ and $x=m$ for now). Using Vandermonde's identity, this simplifies to
    489 
    490 $\binom{y+n+x-(r-l)-3}{x+y-3}$
    491 
    492 As a further optimization, note that everything above is a constant except for $r-l$, which is dependent on the size of the interval. Therefore, we are motivated to loop over the size of $r-l$. Note that the above should also be multiplied by the minimum weight on the interval from $l$ to $r$. Therefore, our problem is now trying to find the sum of minimum of all length $k$ subarrays for all $k$ from $1$ to $n$.
    493 
    494 To solve this subproblem, we can use a monotonic stack to calculate the bounds in which $i$ is the minimum (to break ties, we use strict inequality on one side but not the other). Then, noting that the contribution of an index for $k$ increases by $1$ until some point, then decreases by $1$. This can be optimized by creating the $2$-nd order difference array. The problem is solved in $O(n)$ time.
    495 
    496 Thanks to [Dragos](/profile/Dragos "Grandmaster Dragos") for writing up the following solution.
    497 
    498 **Solution 2**
    499 
    500 First, let’s count nondecreasing arrays.
    501 
    502 How many nondecreasing arrays of length $n$ have last element exactly $m$?
    503 
    504 This is a classical problem. Instead of looking at the array itself, look at its difference variables: $d_1 = a_1 - 1$ and $d_i = a_i - a_{i-1}$ for $i \ge 2$. Since the array is nondecreasing, every $d_i$ is non-negative, and $d_1 + d_2 + \cdots + d_n = a_n - 1 = m - 1.$ So this becomes the standard stars-and-bars count.
    505 
    506 What about arrays where the last element is $\le m$?
    507 
    508 This is equivalent to having $n$ non-negative variables with sum $\le m-1$. The standard trick is to introduce one extra variable that absorbs the remaining value, so this becomes counting $n+1$ non-negative variables with sum exactly $m-1$.
    509 
    510 Now let’s solve the original problem. We simulate the binary search and go through all intervals $[l,r]$ that can appear in the recursion tree. For each such interval, let $mid = \lfloor (l+r)/2 \rfloor$. We count how many arrays make the search terminate at this state, and multiply that count by the current depth of the search.
    511 
    512 Suppose we are at interval $[l,r]$. To terminate here, we need $a_{mid}$ to be the searched value. Also, if $l \gt 1$ then the search must previously have inspected position $l-1$ and concluded that its value is smaller than the target, so we need $a_{l-1} \lt a_{mid}$. Similarly, if $r \lt n$ then we need $a_{mid} \lt a_{r+1}$. Since we are already counting only nondecreasing arrays, these are the only extra constraints that matter.
    513 
    514 So we are left with the following question: how many good arrays satisfy $a_{l-1} \lt a_{mid} \lt a_{r+1}$?
    515 
    516 Let $S = \binom{n+m-1}{n}$ be the number of all good arrays. We now remove the bad arrays by inclusion-exclusion.
    517 
    518 The bad arrays are those with $a_{l-1} = a_{mid}$ or $a_{mid} = a_{r+1}$. The condition $a_{l-1} = a_{mid}$ means that every difference variable corresponding to positions $l, l+1, \dots, mid$ must be $0$. So we can count such arrays by simply removing those variables from the stars-and-bars count. Similarly, the condition $a_{mid} = a_{r+1}$ means that every difference variable corresponding to positions $mid+1, mid+2, \dots, r+1$ must be $0$, and we count those in the same way.
    519 
    520 Finally, we add back the arrays counted twice, namely those with $a_{l-1} = a_{mid} = a_{r+1}$, which is equivalent to forcing all difference variables for positions $l, l+1, \dots, r+1$ to be $0$.
    521 
    522 One last thing to note is that if $l=1$ (or $r=n$), then the corresponding boundary restriction does not exist, so we do not subtract that case.
    523 
    524 Since there are $O(n)$ intervals, and each interval can be computed in $O(1)$, the final complexity is $O(n)$.
    525 
    526 **Code (Solution 1)**
    527 
    528 ```
    529 #include <bits/stdc++.h>
    530 
    531 using namespace std;
    532 
    533 // using namespace std;
    534 using ll = long long;
    535 #define vt vector
    536 #define int long long
    537 #define add push_back 
    538 #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
    539 #define F0R(i,a) FOR(i,0,a)
    540 #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
    541 #define R0F(i,a) ROF(i,0,a)
    542 const ll mod = 676767677;
    543 const ll inf = 1e18;
    544 template<typename T> using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>; //defines min_pq
    545 
    546 mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
    547 int rand_num(int l, int r) {
    548     return rnd()%(r-l+1)+l;
    549 }
    550 int bexpo(int b, int e) {
    551     int ans = 1;
    552     while(e) {
    553         if(e&1) ans=ans*b%mod;
    554         e>>=1;
    555         b=b*b%mod;
    556     }
    557     return ans;
    558 }
    559 signed main() {
    560     ios_base::sync_with_stdio(false); 
    561     cin.tie(0);
    562     // freopen("input.txt" , "r" , stdin);
    563     // freopen("output.txt" , "w", stdout);
    564     int t;
    565     cin >> t;
    566     vt<int> fact(2e6+5), ifact(2e6+5);
    567     fact[0]=ifact[0]=1;
    568     FOR(i, 1, 2e6+5) {
    569         fact[i]=fact[i-1]*i%mod;
    570         ifact[i]=bexpo(fact[i], mod-2);
    571     }
    572     auto nck = [&](int n, int k)->int{
    573         if(k<0 || k>n) {
    574             return 0;
    575         }
    576         return fact[n]*ifact[k]%mod*ifact[n-k]%mod;
    577     };
    578     while(t--) {
    579         int n,m;
    580         cin >> n >> m;
    581         vt<int> time(n);
    582         auto fill = [&](auto self, int l, int r, int start)->void{
    583             if(l>r) return;
    584             int mid = (l+r)/2;
    585             time[mid]=start;
    586             self(self, l, mid-1, start+1);
    587             self(self, mid+1, r, start+1);
    588         };
    589         fill(fill, 0, n-1, 1);
    590         vt<int> l(n,-1),r(n, n);
    591         stack<int> s;
    592         F0R(i, n) {
    593             while(s.size() && time[s.top()]>time[i]) {
    594                 r[s.top()]=i;
    595                 s.pop();
    596             }
    597             s.push(i);
    598         }
    599         while(s.size()) s.pop();
    600         R0F(i, n) {
    601             while(s.size() && time[s.top()]>=time[i]) {
    602                 l[s.top()]=i;
    603                 s.pop();
    604             }
    605             s.push(i);
    606         }
    607         // cout << time << " " << l << " " << r << endl;
    608         vt<int> v(n+10);
    609         F0R(i, n) {
    610             // cout << i << endl;
    611             int left = i-l[i]-1;
    612             int right = r[i]-i-1;
    613             if(left>right) swap(left,right);
    614             v[1]+=time[i];
    615             v[left+2]-=time[i];
    616             v[right+2]-=time[i];
    617             v[left+right+3]+=time[i];
    618         }
    619         FOR(i, 1, n+1) v[i]+=v[i-1];
    620         FOR(i, 1, n+1) v[i]+=v[i-1];
    621         // cout << v << endl;
    622         int ans = 0;
    623         FOR(sz, 1, n+1) {
    624             int out = n-sz;
    625             ans+=v[sz]*nck(out+m-2, m-3)%mod;
    626         }
    627         int mn = inf;
    628         F0R(i, n) {
    629             mn=min(mn, time[i]);
    630             ans+=nck(n-i-1+m-2, m-2)*mn;
    631             ans%=mod;
    632         }
    633         mn = inf;
    634         R0F(i, n) {
    635             mn=min(mn, time[i]);
    636             ans+=nck(i+m-2, m-2)*mn;
    637             ans%=mod;
    638         }
    639         cout << ans << endl;
    640     }
    641     return 0;
    642 ```
    643 
    644 }
    645 
    646 **Code (Solution 2)**
    647 
    648 ```
    649 #include <bits/stdc++.h>
    650 using namespace std;
    651 typedef long long ll;
    652 typedef vector<int> vi;
    653 typedef pair<int, int> pii;
    654 typedef pair<double, double> pdd;
    655 #define pb push_back
    656 #define mp make_pair
    657 #define fs first
    658 #define sc second
    659 #define rep(i, from, to) for (int i = from; i < (to); ++i)
    660 #define all(x) x.begin(), x.end()
    661 #define sz(x) (int)(x).size()
    662 #define FOR(i, to) for (int i = 0; i < (to); ++i)
    663 typedef vector<vector<int>> vvi;
    664 typedef vector<vector<pii>> vvpi;
    665 typedef vector<ll> vll;
    666 typedef vector<vll> vvll;
    667 typedef vector<pair<int, int>> vpi;
    668 typedef pair<ll, ll> pll;
    669 #define MOD 676767677
    670 
    671 template<int MODX>
    672 struct ModInt {
    673   unsigned x;
    674   ModInt() : x(0) { }
    675   ModInt(signed sig) : x(((sig%MODX)+MODX)%MODX) {  }
    676   ModInt(signed long long sig) : x(((sig%MODX)+MODX)%MODX) { }
    677   int get() const { return (int)x; }
    678   ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
    679  
    680   ModInt &operator+=(ModInt that) { if ((x += that.x) >= MODX) x -= MODX; return *this; }
    681   ModInt &operator-=(ModInt that) { if ((x += MODX - that.x) >= MODX) x -= MODX; return *this; }
    682   ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MODX; if (x < 0) x += MODX; return *this; }
    683   ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MODX - 2); }
    684  
    685   ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    686   ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    687   ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    688   ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    689   bool operator<(ModInt that) const { return x < that.x; }
    690   friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
    691 };
    692 typedef ModInt<MOD> mint;
    693 
    694 // N ~ 10^6
    695 class Combinations {
    696 public:
    697   vector<mint> inv, fact, ifact;
    698 
    699   Combinations(int N) {
    700     inv.resize(N+10), fact.resize(N+10), ifact.resize(N+10);
    701     inv[1] = fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
    702     for(int i=2;i<=N;++i) {
    703       inv[i] = inv[MOD%i] * (MOD - MOD/i);
    704       fact[i] = fact[i-1]*i;
    705       ifact[i] = ifact[i-1]*inv[i];
    706     }
    707   }
    708   // a > b
    709   mint comb(ll a, ll b) {
    710     if(a < b) return mint(0);
    711     return fact[a] * ifact[b] * ifact[a-b];
    712   }
    713 };
    714 
    715 Combinations comb(2010100);
    716 
    717 // Stars and bars
    718 mint SB(int K, int S) {
    719   return comb.comb(S+K-1, K-1);
    720 }
    721 
    722 int n,m;
    723 mint ret = 0;
    724 void dfs(int l, int r, int depth) {
    725   if (l > r) return;
    726   // Last two checked positions.
    727   int lp = l - 1;
    728   int rp = r + 1;
    729   
    730   int mid = (l + r)/2;
    731   mint TOT = SB(n+1, m);
    732   ret += TOT * depth;
    733   // If we saw a position for which ARR[l-1] < ARR[mid]
    734   if (lp != -1) {
    735     ret -= SB(n+1 - (mid - lp), m) * depth;
    736   }
    737 
    738   // If we saw a position for which a[mid] < a[r+1]
    739   if (rp != n) {
    740     ret -= SB(n+1 - (rp - mid), m) * depth;
    741   }
    742 
    743   // If we saw both a[l-1] < a[mid] < a[r+1] add the double counted arrays back
    744   if (lp != -1 && rp != n) {
    745     ret += SB(n + 1 - (rp - lp), m) * depth;
    746   }
    747   dfs(mid+1, r, depth+1);
    748   dfs(l, mid-1, depth+1);
    749 }
    750 
    751 int main() {
    752   cin.sync_with_stdio(0);
    753   cin.tie(0);
    754   int T;
    755   cin >> T;
    756   while(T--) {
    757     cin >> n >> m;
    758     --m;
    759     ret = 0;
    760     dfs(0, n-1, 1);
    761     cout << ret << "\n";
    762   }
    763   return 0;
    764 }
    765 ```
    766 
    767 **Bonus**
    768 
    769 Solve this problem for $n,m \lt =10^6$ but there is no limit on sum of $n$ or $m$ across all test cases.
    770 
    771 **Rate The Problem!**
    772 
    773 * Good Problem
    774 * Okay Problem
    775 * Bad Problem
    776 * Didn't Solve
    777 
    778 #### [2211G - Rational Bubble Sort](/contest/2211/problem/G)
    779 
    780 Problem credits: [chromate00](/profile/chromate00 "Expert chromate00"). Special thanks: [BurnedChicken](/profile/BurnedChicken "Legendary Grandmaster BurnedChicken")
    781 
    782 **Hint 1**
    783 
    784 Consider the graph of prefix sums.
    785 
    786 **Solution**
    787 
    788 Let's take the prefix sums $b_i=a_1+a_2+\ldots+a_i$ instead of $a_i$ (including $b_0=0$), and consider what it means when $a_i$ is sorted in non-decreasing order. We can see that $a_i$ being non-decreasing is equivalent to the points $(i,b_i)$ forming a chain that is convex from below. The operation on index $i$ makes the segment from $(i-1,b_{i-1})$ to $(i+1,b_{i+1})$ completely straight, and to sort $a$ we need to be able to make the chain convex using the operation.
    789 
    790 Notice the following observation.
    791 
    792 * Observation: any chain $(i-1,b_{i-1}),(i,b_i),\ldots,(j,b_j)$ can be made arbitrarily close to the line from $(i-1,b_{i-1})$ to $(j,b_j)$.
    793 
    794 In other words, $a_i,a_{i+1},\ldots,a_j$ can be made arbitrarily close to their average value.
    795 
    796 Because their mean is constant when we don't perform operations outside this range, we can easily reason about their variance. Let's say their mean is $\mu$. Then, $(a_i-\mu)^2+(a_{i+1}-\mu)^2 \ge 2 \cdot (\frac{a_i+a_{i+1}}{2}-\mu)^2$ due to the convexity of the function $f(x)=(x-\mu)^2$. Equality holds if and only if $a_i=a_{i+1}$. In other words, as long as there is at least one unequal adjacent pair (unless all $j-i+1$ values are equal, there definitely will be one), the variance can decrease indefinitely (that is, arbitrarily close to $0$). The variance becomes $0$ if and only if all $j-i+1$ values are equal.
    797 
    798 Now, let's see if there is a point $(i,b_i)$ strictly below the line from $(0,0)$ to $(n,b_n)$. Then, we can make the segments almost straight from $(0,0)$ to $(i,b_i)$ and from $(i,b_i)$ to $(n,b_n)$. The fact that we can make a segment almost (yet not completely) straight is important. After we make them straight enough, let's call their slopes $\mu_{1,l}$ and $\mu_{1,r}$, and we can perform the operation on index $i$ so that the segment from $(i-1,b_{i-1})$ to $(i+1,b_{i+1})$ is straight. This slope $s_{1,1}$ certainly satisfies $\mu_l \lt s_{1,1} \lt \mu_r$. If this does not hold, then we could certainly go back, make the segments flatter, and it will definitely hold at some point when we perform the operation on index $i$.
    799 
    800 We'll now set $l=i-1$, $r=i+1$, and maintain an invariant that the segment $[l,r]$ is convex. If we perform the operation on indices $i-1$ and $i+1$, we get two slopes $s_{2,1}$ and $s_{2,2}$ such that $\mu_{2,l} \lt s_{2,1} \lt s_{2,2} \lt \mu_{2,r}$, where $\mu_{2,l}$ is the slope from $(0,0)$ to $(l-1,b_{l-1})$ and $\mu_{2,r}$ is the slope from $(r+1,b_{r+1})$ to $(n,b_n)$. We have now expanded the segment to $[l-1,r+1]$ while maintaining convexity.
    801 
    802 Repeating this process, we can expand $[l,r]$ to $[0,n]$, and the chain can become entirely convex.
    803 
    804 Now the only case left is when all points are either on or above the line from $(0,0)$ to $(n,b_n)$. We can only make them non-decreasing by making them all equal. However, if two consecutive points are above the line, we can't put them right on the line because we're still moving a point to somewhere above the line. However, if only one point $(i,b_i)$ is above the line, we can make the segment from $(i-1,b_{i-1})$ to $(i+1,b_{i+1})$ completely straight. Therefore, if there are no two consecutive points above the line, we can perform the operation on all points above the line, and the chain will be completely straight. We have shown that the outlined two cases are the only cases in which we can make $a$ sorted in non-decreasing order.
    805 
    806 The problem is solved in $\mathcal{O}(n)$ time.
    807 
    808 **Code**
    809 
    810 ```
    811 #include<bits/stdc++.h>
    812 using namespace std;
    813 using ll=long long;
    814 using pii=pair<int,int>;
    815 
    816 #define all(a) a.begin(),a.end()
    817 #define pb push_back
    818 #define sz(a) ((int)a.size())
    819 
    820 signed main(){
    821   ios_base::sync_with_stdio(0),cin.tie(0);
    822   int t;cin>>t;
    823   while(t--)
    824   {
    825     ll n; cin >> n;
    826     vector<ll> a(n);
    827     for(int i=0; i<n; ++i) cin >> a[i];
    828     vector<ll> sum(n+1);
    829     for(int i=0; i<n; ++i) sum[i+1]=sum[i]+a[i];
    830     vector<ll> exact(n+1);
    831     exact[0]=exact[n]=1;
    832     bool found=0;
    833     for(int i=1; i<n; ++i){
    834         if(1ll*sum[i]*(n-i)<1ll*(sum[n]-sum[i])*i){
    835             cout << "Yes\n";
    836             found=1;break;
    837         }
    838         if(1ll*sum[i]*(n-i)==1ll*(sum[n]-sum[i])*i){
    839             exact[i]=1;
    840         }
    841     }
    842     if(found)continue;
    843     for(int i=0; i+1<=n; ++i){
    844         if(!exact[i]&&!exact[i+1]){
    845             cout << "No\n";
    846             found=1;break;
    847         }
    848     }
    849     if(found)continue;
    850     cout << "Yes\n";
    851   }
    852 }
    853 ```
    854 
    855 **Rate The Problem!**
    856 
    857 * Good Problem
    858 * Okay Problem
    859 * Bad Problem
    860 * Didn't Solve
    861 
    862 #### [2211H - Median Deletion](/contest/2211/problem/H)
    863 
    864 Problem credits: [nifeshe](/profile/nifeshe "Grandmaster nifeshe")
    865 
    866 **Hint 1**
    867 
    868 We can reduce a fixed subarray $[l, r]$ of $p$ to two elements: the minimum and the maximum.
    869 
    870 **Hint 2**
    871 
    872 The answer is at most $5$. Try to determine whether we can get the answer of $4$.
    873 
    874 **Hint 3**
    875 
    876 Consider the minimum/maximum in $[1, i - 1]$ and minimum/maximum in $[i + 1, n]$. There is only one non-trivial case: $[1, 4, 3, 5, 2, 6]$ for $p_i = 3$.
    877 
    878 **Hint 4**
    879 
    880 Let $a, b$ be the positions of prefix minimum and prefix maximum in $[1, i - 1]$ accordingly, and $c, d$ be the positions suffix minimum and suffix maximum. WLOG assume that $a \lt b$. The case is $a \lt b \lt i \lt c \lt d$, WLOG assume we have to remove $p_b$ using an element from $[i + 1, c - 1]$.
    881 
    882 **Hint 5**
    883 
    884 Apart from the trivial cases the condition is this: let $l = \max(a, b)$ and $r = \min(c, d)$, then the answer is $\le 4$ iff there is an element $l \le j \le r$ such that $p_j \lt \min(p_l, p_r)$ or $p_j \gt \max(p_l, p_r)$.
    885 
    886 **Hint 6**
    887 
    888 To determine if it's $3$ consider two cases: $\text{pos}_1 \lt i \lt \text{pos}_n$ and $\text{pos}_1 \lt \text{pos}_n \lt i$. The first case is significantly easier.
    889 
    890 **Hint 7**
    891 
    892 If the answer is at most $4$ when $\text{pos}_1 \lt i \lt \text{pos}_n$, we can reduce $[\text{pos}_1, \text{pos}_n]$ to only $[1, p_i, n]$.
    893 
    894 **Hint 8**
    895 
    896 If there is an extremum before $\text{pos}_1$ or after $\text{pos}_n$, we can't do anything about it. Now consider the $\text{pos}_1 \lt \text{pos}_n \lt i$ case.
    897 
    898 **Hint 9**
    899 
    900 The two main cases are: $[1, n, p_i, H, L]$ and $[1, n, p_i, L, H]$, where $L = p_c$ and $H = p_d$. Consider $[1, n, p_i, L, H]$ first.
    901 
    902 **Hint 10**
    903 
    904 We can remove any element bigger than $p_i$ using $n$. Since the answer is at least $4$, we can remove $L$. After that we remove $H$ using $n$, so the answer is $3$. Now consider $[1, n, p_i, H, L]$
    905 
    906 **Hint 11**
    907 
    908 We could easily remove $H$ using $n$, however after that we wouldn't be able to remove $L$. It is sometimes possible to remove both, consider $p = [1, 7, 2, 6, 4, 5, 3]$ for $p_i = 4$.
    909 
    910 **Hint 12**
    911 
    912 We do $[1, 7, 2, 6, 4, 5, 3] \rightarrow [1, 7, 2, 6, 4, 3] \rightarrow [1, 7, 2, 4, 3] \rightarrow [1, 7, 2, 4, 3] \rightarrow [1, 7, 2, 4] \rightarrow [1, 7, 4]$. So we need to find indices $j$ and $k$ such that: $\text{pos}_n \lt k \lt j \lt i$, $p_k \lt L \lt p_i \lt H \lt p_j$, and we can first clear $[j + 1, i - 1]$ and then clear $[k + 1, j]$. Greedy does not work as we have to be able to clear the intervals. For example, for $p = [1, 8, 3, 7, 2, 5, 6, 4]$ and $p_i = 5$ the answer is $4$, not $3$, as we cannot remove $2$ after choosing $p_k = 3$ and $p_j = 7$.
    913 
    914 **Hint 13**
    915 
    916 Choose $k$ to be the minimum in $[\text{pos}_n, i]$, $j$ to be the maximum in $[k + 1, i]$, then you can always clear the intervals.
    917 
    918 **Solution**
    919 
    920 First of all, we trivially can never delete $1$ or $n$, since they are always the smallest and the largest elements. Furthermore, for a fixed subarray $[l, r]$, where $p_x$ is the minimum and $p_y$ is the maximum in the subarray, we can trivially turn it $[p_l, p_{l + 1}, \ldots, p_r]$ into $[p_x, p_y]$ or $[p_y, p_x]$ (depending on their order) by continuously applying operation on the subarray. We call that sequence operations **a reduction** of $[l, r]$.
    921 
    922 From this immediately follows that the answer for any $p_i$ is at most $5$: leave at most $2$ elements in $[1, i - 1]$, leave $p_i$, and at most $2$ elements in $[i + 1, n]$. Moreover, if $p_i$ is not $1$ or $n$, the answer is at least $3$, since we can't delete $1$ or $n$. Therefore, the problem is determining whether the answer is $3$, $4$ or $5$ (for $p_i = 1$ or $p_i = n$ it is trivially $2$).
    923 
    924 Let's try to determine if we can get an answer $\le 4$ first. Let's get rid of the trivial cases first: if $p_i$ is suffix/prefix minimum/maximum, one of $[1, i]$ or $[i, n]$ can be reduced to only $2$ elements, and the other part can be reduced to $2$ elements as well, so an answer of $4$ can be trivially achieved.
    925 
    926 Now assume that $p_i$ is not a suffix/prefix minimum/maximum. Let $a, b$ be the positions of prefix minimum and prefix maximum in $[1, i - 1]$ accordingly, and $c, d$ be the positions suffix minimum and suffix maximum. WLOG assume that $a \lt b$, so the prefix minimum appears earlier than the prefix maximum.
    927 
    928 Notice that since $i$ is not an extrema we must have $p_a, p_c \lt p_i \lt p_b, p_d$. Therefore, if $d \lt c$ we can reduce both $[1, i - 1]$ and $[i + 1, n]$, and then do an operation on $[p_b, p_i, p_d]$ which will delete either $p_b$ or $p_d$ and achieve an answer of $4$.
    929 
    930 Therefore assume that the elements are positioned as $[\ldots, p_a, \ldots, p_b, \ldots, p_i, \ldots, p_c, \ldots, p_d, \ldots]$. Notice that we cannot remove $p_a$ or $p_d$ without removing $p_i$, $p_b$ or $p_c$. For example to delete $p_a$ we need an element greater than $p_a$, and the next one can only be located after $p_i$, so we have to remove either $p_b$ or $p_i$.
    931 
    932 Therefore we need to remove $p_b$ or $p_c$. WLOG assume that we are trying to remove $p_b$ first. We cannot do that only with elements in $[1, i]$, so assume that we use an index $i \lt j \lt c$ for that. We perform an operation on $[p_b, p_i, p_j]$. This deletes $p_b$ iff $p_b \lt p_j$.
    933 
    934 Therefore, there needs be an index $j$ satisfying $i \lt j \lt c$ and $p_j \gt p_b$ for $p_b$ to be deletable. For simplicity, take $j$ to be the maximum of $[i, c]$. Then we can achieve an answer of $4$ this way: reduce $[i + 1, c]$ which will leave us with $[p_j, p_c]$, reduce $[1, i - 1]$, reduce $[c, n]$. After this we end up with $[p_a, p_b, p_i, p_j, p_c, p_d]$. Remove $p_b$ in $[p_b, p_i, p_j]$ and then remove $p_j$ in $[p_j, p_c, p_d]$. At the end we will have $[p_a, p_i, p_c, p_d]$.
    935 
    936 The case of removing $p_c$ is identical. Therefore we have a complete solution for determining whether the answer is $\le 4$. A simple way to frame it is this: let $l$ be $\max(a, b)$ and $r$ be $\min(c, d)$. The answer is $3$ or $4$ iff one of the following holds: $i = l$, $i = r$, $\max([p_l, p_{l + 1}, \ldots, p_r]) \gt \max(p_l, p_r)$ or $\min([p_l, p_{l + 1}, \ldots, p_r]) \lt \min(p_l, p_r)$. The last two conditions mean that there is an element that we can use to remove $p_l$ or $p_r$.
    937 
    938 Now we have to determine if the answer is $3$ or $4$. From now assume that the condition above holds. Note that to get $3$ we have to end up with exactly $3$ elements: $1$, $n$ and $p_i$. Denote $\text{pos}_x = i$ as $i$ such that $p_i = x$. WLOG assume that $\text{pos}_1 \lt \text{pos}_n$. Consider two cases: $\text{pos}_1 \lt i \lt \text{pos}_n$ and $\text{pos}_n \lt i$. The case of $\text{pos}_1 \gt i$ is identical to $\text{pos}_n \lt i$.
    939 
    940 Consider $\text{pos}_1 \lt i \lt \text{pos}_n$ first. Notice that we can remove everything in $[\text{pos}_1, \text{pos}_n]$ while keeping $p_i$. Since the answer is $\le 4$ we can leave at most $4$ elements in $[\text{pos}_1, \text{pos}_n]$, let them be $1$, $n$, $p_i$ and $p_j$. Then if $p_i \lt p_j$ we remove $p_j$ using $n$ and if $p_i \gt p_j$ we remove it using $1$. Therefore we only need to make sure that there is nothing left in $[1, \text{pos}_1 - 1]$ and $[\text{pos}_n + 1, n]$.
    941 
    942 Remember that we already proved that if the prefix maximum of $[1, i]$ is in $[1, \text{pos}_1 - 1]$ we cannot remove it without removing $1$, and if the suffix minimum of $[i, n]$ is in $[\text{pos}_n + 1, n]$ we cannot remove it without removing $n$.
    943 
    944 Therefore let $b$ be the index of prefix maximum in $[1, i]$ and $c$ be the index of prefix minimum in $[i, n]$. The answer is $3$ iff $b \ge \text{pos}_1$ and $c \le \text{pos}_n$ and $4$ otherwise.
    945 
    946 Now the last case is $\text{pos}_1 \lt \text{pos}_n \lt i$. Let $a$ be the suffix minimum of $[i, n]$ and $b$ be the suffix maximum, and $p_a = L$ and $p_b = H$.
    947 
    948 Let's get rid of trivial cases. If $a = i$ we can reduce $[\text{pos}_n, n]$ and then $[1, \text{pos}_n]$ to get an answer of $3$. If $b = i$ we need to remove $p_a$ with something in $[\text{pos}_n, i - 1]$. Similarly to our solution for $\le 4$ we need $\min(p_{\text{pos}}, \ldots, p_{i - 1}) \lt p_a$ for this, which is sufficient.
    949 
    950 Now assume $a \neq i$ and $b \neq i$. If $a \lt b$, since the answer is $\le 4$ we can remove $p_a$ using $[\text{pos}_n, i - 1]$, so the case is the same as $a = i$ and is always $3$.
    951 
    952 The only case left is $b \lt a$, which is $[1, n, p_i, H, L]$. We need to remove $H$ using $[\text{pos}_n, i - 1]$ and then remove $L$ using that same interval. Assume we will remove $H$ using $p_j$ and $L$ using $p_k$.
    953 
    954 To do this we need to have $p_k \lt L \lt H \lt p_j$. Since we first remove $H$ then $L$, we need to clear $[j + 1, i - 1]$ without removing $p_k$, therefore we also need to have $k \lt j$. We also need to clear $[k + 1, j]$ after that to remove $L$.
    955 
    956 Claim: it is optimal to choose $k$ to be the index of minimum in $[\text{pos}_n, i]$. Suppose we don't and the index of the minimum is $l$.
    957 
    958 If we choose $k \lt l$ we cannot clear $[k + 1, j]$ since we cannot delete $l$: $[i + 1, b - 1]$ can't be used for that because it needs to be cleared to remove $H = p_b$, and $[1, \text{pos}_n - 1]$ can't be used as well because $n$ and $p_k$ cannot be removed.
    959 
    960 Therefore, $p_k \ge p_l$ and $p_j \le \max(p_{l + 1}, \ldots, p_i)$. Notice that choosing $k$ and $j$ to be exactly these value is always optimal: we can clear $[j + 1, i - 1]$ by reducing $[k, i - 1]$, and then remove $p_j$ in $[n, p_k, p_j]$. Since we need to have $p_k \lt L \lt H \lt p_j$, minimizing $p_k$ and maximizing $p_j$ is needed.
    961 
    962 Therefore, the condition is: let $k$ be the minimum in $[\text{pos}_n, i]$ and $j$ be the maximum in $[k + 1, i]$. Then the answer is $3$ iff $p_k \lt L \lt H \lt p_j$ and $4$ otherwise. This covers all the cases and solves the problem.
    963 
    964 The final solution is $O(n)$ or $O(n \log n)$ depending on the implementation. It can be implemented without considering too much symmetrical cases, refer to the code below.
    965 
    966 **Code**
    967 
    968 ```
    969 #include <bits/stdc++.h>
    970 
    971 using namespace std;
    972 
    973 const int LG = 20;
    974 
    975 vector<int> get_default(vector<int> p) {
    976     int n = p.size();
    977     vector<int> pos(n + 1);
    978     for(int i = 0; i < n; i++) pos[p[i]] = i;
    979 
    980     vector<int> ans(n, 5);
    981 
    982     int pos_1 = pos[1], pos_n = pos[n];
    983     if(pos_1 > pos_n) return ans;
    984 
    985     vector<int> pos_suff_min(n, n - 1), pos_suff_max(n, n - 1);
    986     for(int i = n - 2; ~i; i--) {
    987         pos_suff_min[i] = pos_suff_min[i + 1];
    988         if(p[i] < p[pos_suff_min[i]]) pos_suff_min[i] = i;
    989 
    990         pos_suff_max[i] = pos_suff_max[i + 1];
    991         if(p[i] > p[pos_suff_max[i]]) pos_suff_max[i] = i;
    992     }
    993 
    994     vector<int> pos_pref_min(n), pos_pref_max(n);
    995     for(int i = 1; i < n; i++) {
    996         pos_pref_min[i] = pos_pref_min[i - 1];
    997         if(p[i] < p[pos_pref_min[i]]) pos_pref_min[i] = i;
    998 
    999         pos_pref_max[i] = pos_pref_max[i - 1];
   1000         if(p[i] > p[pos_pref_max[i]]) pos_pref_max[i] = i;
   1001     }
   1002 
   1003     vector<vector<int>> t_min(n, vector<int>(LG));
   1004     for(int i = 0; i < n; i++) t_min[i][0] = p[i];
   1005     for(int l = 1; l < LG; l++) {
   1006         for(int i = 0; i + (1 << l) <= n; i++) {
   1007             t_min[i][l] = min(t_min[i][l - 1], t_min[i + (1 << l - 1)][l - 1]);
   1008         }
   1009     }
   1010     auto get_min = [&](int l, int r) {
   1011         int L = __lg(r - l + 1);
   1012         return min(t_min[l][L], t_min[r - (1 << L) + 1][L]);
   1013     };
   1014 
   1015     vector<vector<int>> t_max(n, vector<int>(LG));
   1016     for(int i = 0; i < n; i++) t_max[i][0] = p[i];
   1017     for(int l = 1; l < LG; l++) {
   1018         for(int i = 0; i + (1 << l) <= n; i++) {
   1019             t_max[i][l] = max(t_max[i][l - 1], t_max[i + (1 << l - 1)][l - 1]);
   1020         }
   1021     }
   1022     auto get_max = [&](int l, int r) {
   1023         int L = __lg(r - l + 1);
   1024         return max(t_max[l][L], t_max[r - (1 << L) + 1][L]);
   1025     };
   1026 
   1027     for(int i = pos_1; i < n; i++) {
   1028         if(p[i] == 1 || p[i] == n) {
   1029             ans[i] = 2;
   1030             continue;
   1031         }
   1032         if(i == 0 || i == n - 1) {
   1033             ans[i] = 3;
   1034             continue;
   1035         }
   1036 
   1037         int a = pos_pref_min[i], b = pos_pref_max[i];
   1038         int c = pos_suff_min[i], d = pos_suff_max[i];
   1039         int l = max(a, b), r = min(c, d);
   1040         int min_all = get_min(l, r), max_all = get_max(l, r);
   1041         if(l == i && r == i) {
   1042             ans[i] = 3;
   1043             continue;
   1044         }
   1045 
   1046         if(l == i || r == i) ans[i] = 4;
   1047         if(abs(p[r] - p[l]) != max_all - min_all) ans[i] = 4;
   1048         if(ans[i] != 4) continue;
   1049 
   1050         // 1 p[i] n
   1051         if(i < pos_n) {
   1052             // H 1 p[i] n
   1053             if(b < pos_1) continue;
   1054             // 1 p[i] n L
   1055             if(c > pos_n) continue;
   1056             ans[i] = 3;
   1057             continue;
   1058         }
   1059 
   1060         // 1 n p[i]
   1061 
   1062         // 1 n p[i] H
   1063         if(pos_suff_min[i] == i) ans[i] = 3;
   1064         // 1 n p[i] L H, can't remove L
   1065         if(get_min(l, i) > p[pos_suff_min[i]]) continue;
   1066         // 1 n p[i] L, can remove L
   1067         if(r == i) ans[i] = 3;
   1068         // 1 n p[i] L H, first remove L, then H
   1069         if(c < d) ans[i] = 3;
   1070 
   1071         // 1 n p[i] H L, pick k and j
   1072         int k = pos[get_min(pos_n, i)];
   1073         int j = pos[get_max(k, i)];
   1074         if(p[k] < p[c] && p[d] < p[j]) ans[i] = 3;
   1075     }
   1076 
   1077     for(auto &i : ans) i = min(i, n);
   1078     return ans;
   1079 }
   1080 
   1081 vector<int> get(vector<int> p) {
   1082     int n = p.size();
   1083 
   1084     vector<int> ans(n, n);
   1085     for(int t_reverse = 0; t_reverse < 2; t_reverse++) {
   1086         for(int t_invert = 0; t_invert < 2; t_invert++) {
   1087             auto curr_ans = get_default(p);
   1088             if(t_reverse) reverse(curr_ans.begin(), curr_ans.end());
   1089             for(int i = 0; i < n; i++) ans[i] = min(ans[i], curr_ans[i]);
   1090 
   1091             for(auto &i : p) i = n + 1 - i;
   1092         }
   1093         reverse(p.begin(), p.end());
   1094     }
   1095     return ans;
   1096 }
   1097 
   1098 void solve() {
   1099     int n;
   1100     cin >> n;
   1101     vector<int> p(n);
   1102     for(auto &i : p) {
   1103         cin >> i;
   1104     }
   1105 
   1106     auto ans = get(p);
   1107     for(auto i : ans) cout << i << " "; cout << '\n';
   1108 }
   1109 
   1110 signed main() {
   1111     ios_base::sync_with_stdio(0); cin.tie(0);
   1112     int ttt = 1;
   1113     cin >> ttt;
   1114     while(ttt--) {
   1115         solve();
   1116     }
   1117 }
   1118 ```
   1119 
   1120 **Rate The Problem!**
   1121 
   1122 * Good Problem
   1123 * Okay Problem
   1124 * Bad Problem
   1125 * Didn't Solve