codeforces-scrape

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

1536.md (41198B)


      1 Source: https://codeforces.com/blog/entry/91520
      2 
      3 We hope you liked the problems! If you’re curious about the two different problem formats, initially [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani"), [malachi_toney_goat](/profile/malachi_toney_goat "Master malachi_toney_goat"), [qlf9](/profile/qlf9 "Candidate Master qlf9") and I were working on Omkar 3 with [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o") while [gotexans](/profile/gotexans "Master gotexans") was working on a separate round with [isaf27](/profile/isaf27 "International Grandmaster isaf27"). We eventually decided to join forces and combine the rounds, resulting in the current Omkar 3.
      4 
      5 # [1536A - Omkar and Bad Story](/contest/1536/problem/A "Codeforces Round 724 (Div. 2)")
      6 
      7 Idea: [rabaiBomkarBittalBang](/profile/rabaiBomkarBittalBang "Candidate Master rabaiBomkarBittalBang")
      8 
      9 Preparation: [rabaiBomkarBittalBang](/profile/rabaiBomkarBittalBang "Candidate Master rabaiBomkarBittalBang"), [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani"), [qlf9](/profile/qlf9 "Candidate Master qlf9")
     10 
     11 [Video editorial](https://www.youtube.com/watch?v=GZeihS2xTSc)
     12 
     13 **Hint**
     14 
     15 Consider what happens when $a$ contains a negative number.
     16 
     17 **Solution**
     18 
     19 We first claim that if any negative number exists in $a$, then no solution exists. Denote $p$ as the smallest number in $a$ and $q$ as another arbitrary number in the array (as $n \geq 2$, $q$ always exists). Clearly, $|q - p| = q - p \gt 0$. However, because $p$ is negative, $q - p \gt q$. As such, adding $q - p$ to the output array would create the pair $(q - p, p)$ with difference $q - 2p \gt q - p$. We have the same problem as before; thus, it is impossible to create a *nice* array if there exists a negative number in $a$.
     20 
     21 After we deal with this case, we now claim that $b = [0, 1, 2, ..., 100]$ is a valid *nice* array for any $a$ that contains no negative numbers. It is easy to verify that this is a valid *nice* array. And since in this case, every element of $a$ is nonnegative and distinct, it is always possible to rearrange and add elements to $a$ to obtain $b$.
     22 
     23 **Implementation in Java by rabaiBomkarBittalBang**
     24 
     25 ```
     26 //DecimalFormat f = new DecimalFormat("##.00");
     27 
     28 import java.util.*;
     29 import java.io.*;
     30 import java.math.*;
     31 import java.text.*;
     32 public class OmkarAndBadStory {
     33     public static void main(String[] omkar) throws Exception
     34     {
     35         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
     36         StringTokenizer st = new StringTokenizer(in.readLine());
     37         StringBuilder sb = new StringBuilder();
     38         int cases = Integer.parseInt(st.nextToken());
     39         for(int i = 0; i < cases; i++)
     40         {
     41             solve(in, st, sb);
     42         }
     43         System.out.print(sb);
     44     }
     45     public static void solve(BufferedReader in, StringTokenizer st, StringBuilder sb) throws Exception
     46     {
     47         int k = Integer.parseInt(in.readLine());
     48         String s = in.readLine();
     49         st = new StringTokenizer(s);
     50         boolean hasneg = false;
     51         int max = 0;
     52         int x;
     53         int[] arr = new int[k];
     54         for(int i = 0; i < k; i++)
     55         {
     56             x = Integer.parseInt(st.nextToken());
     57             arr[i] = x;
     58             if(x < 0)
     59             {
     60                 hasneg = true;
     61             }
     62             else
     63             {
     64                 max = Math.max(max, x);
     65             }
     66         }
     67         if(hasneg)
     68         {
     69             sb.append("NO\n");
     70         }
     71         else
     72         {
     73             sb.append("YES\n");
     74             sb.append((max+1)+"\n");
     75             for(int i = 0; i < max; i++)
     76             {
     77                 sb.append(i + " ");
     78             }
     79             sb.append(max+"");
     80             sb.append("\n");
     81         }
     82     }
     83 
     84 }
     85 ```
     86 
     87 **Implementation in Kotlin by Tlatoani**
     88 
     89 ```
     90 fun main() {
     91     for (c in 1..readLine()!!.toInt()) {
     92         val n = readLine()!!.toInt()
     93         val numberballs = readLine()!!.split(" ").map { it.toInt() }
     94         if (numberballs.min()!! < 0) {
     95             println("nO")
     96         } else {
     97             println("yEs")
     98             println(numberballs.max()!! + 1)
     99             println((0..numberballs.max()!!).joinToString(" "))
    100         }
    101     }
    102 }
    103 ```
    104 
    105 **Implementation in C++ by kefaa2**
    106 
    107 ```
    108 #ifdef DEBUG
    109 #define _GLIBCXX_DEBUG
    110 #endif
    111 #pragma GCC optimize("O3")
    112 #include <bits/stdc++.h>
    113 
    114 using namespace std;
    115 typedef long double ld;
    116 typedef long long ll;
    117 int n;
    118 int main() {
    119     ios_base::sync_with_stdio(false);
    120     cin.tie(nullptr);
    121 //    freopen("input.txt", "r", stdin);
    122     int tst;
    123     cin >> tst;
    124     while (tst--) {
    125         int n;
    126         cin >> n;
    127         bool f = false;
    128         for (int i = 1; i <= n; i++) {
    129             int x;
    130             cin >> x;
    131             if (x < 0) f = true;
    132         }
    133         if (f) {
    134             cout << "NO\n";
    135         }
    136         else {
    137             cout << "YES\n";
    138             cout << 101 << '\n';
    139             for (int i = 0; i <= 100; i++) cout << i << " ";
    140             cout << '\n';
    141         }
    142     }
    143     return 0;
    144 }
    145 ```
    146 
    147 **Implementation in Haskell by Tlatoani**
    148 
    149 ```
    150 import Data.List (intercalate)
    151 import Control.Monad (replicateM)
    152 
    153 main = do t <- read <$> getLine
    154           replicateM t solve
    155 
    156 solve = do getLine
    157            xs <- (map read . words) <$> getLine
    158            putStrLn (if any (< 0) xs then "nO" else ("yEs\n101\n" ++ intercalate " " (map show [0..100])))
    159 ```
    160 
    161 # [1536B - Prinzessin der Verurteilung](/contest/1536/problem/B "Codeforces Round 724 (Div. 2)")
    162 
    163 Idea: [gotexans](/profile/gotexans "Master gotexans")
    164 
    165 Preparation: [gotexans](/profile/gotexans "Master gotexans")
    166 
    167 [Video editorial](https://www.youtube.com/watch?v=--_QUTD7t94)
    168 
    169 **Hint 1**
    170 
    171 Pigeonhole principle
    172 
    173 **Hint 2**
    174 
    175 What is the longest the answer can be?
    176 
    177 **Solution**
    178 
    179 Let’s brute force check all substrings of length <= 3 and print the lexicographically smallest one that doesn’t appear as a substring in the input. We can guarantee that we will come across the answer due to the pigeonhole principle. There are at most $n+n-1+n-2 = 3n-3$ possible substrings of length 3 or shorter in the input. There exist $26+26^2+26^3 = 18278$ total substrings of length 3 or shorter. It is impossible for the input to contain all $18278$ substrings, as $3n-3 \lt 18278$ for $n \leq 1000$.
    180 
    181 Final runtime looks something like $O(18278n)$ or $O(n)$ depending on how you implement substring checking.
    182 
    183 **Implementation in Java by hu_tao**
    184 
    185 ```
    186 //stan hu tao
    187 //come to K-expo!!!
    188 //watch me get carried in nct ridin
    189 import static java.lang.Math.max;
    190 import static java.lang.Math.min;
    191 import static java.lang.Math.abs;
    192 import static java.lang.System.out;
    193 import java.util.*;
    194 import java.io.*;
    195 import java.math.*;
    196 
    197 public class FischlPog
    198 {
    199     public static void main(String hi[]) throws Exception
    200     {
    201         ArrayList<String> ls = new ArrayList<String>();
    202         for(int a=0; a < 26; a++)
    203             ls.add(get(a)+"");
    204         for(int a=0; a < 26; a++)
    205             for(int b=0; b < 26; b++)
    206                 ls.add(get(a)+""+get(b));
    207         for(int a=0; a < 26; a++)
    208             for(int b=0; b < 26; b++)
    209                 for(int c=0; c < 26; c++)
    210                     ls.add(get(a)+""+get(b)+""+get(c));
    211         Collections.sort(ls, (x,y) -> {
    212             int len1 = x.length();
    213             int len2 = y.length();
    214             if(len1 != len2)
    215                 return len1-len2;
    216             return x.compareTo(y);
    217         });
    218         //assume multitests exist
    219         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
    220         StringTokenizer st = new StringTokenizer(infile.readLine());
    221         int T = Integer.parseInt(st.nextToken());
    222         StringBuilder sb = new StringBuilder();
    223         while(T-->0)
    224         {
    225             int N = Integer.parseInt(infile.readLine());
    226             String input = infile.readLine();
    227             HashSet<String> substrings = new HashSet<String>();
    228             for(int len=1; len <= 3; len++)
    229                 for(int i=0; i < N-len+1; i++)
    230                     substrings.add(input.substring(i, i+len));
    231             for(int i=0; i < ls.size(); i++)
    232                 if(!substrings.contains(ls.get(i)))
    233                 {
    234                     sb.append(ls.get(i)+"\n");
    235                     break;
    236                 }
    237         }
    238         System.out.print(sb);
    239     }
    240     public static char get(int a)
    241     {
    242         return (char)(a+'a');
    243     }
    244 }
    245 ```
    246 
    247 **Implementation in Kotlin by Tlatoani**
    248 
    249 ```
    250 fun main() {
    251     repeat(readLine()!!.toInt()) {
    252         val n = readLine()!!.toInt()
    253         val s = readLine()!!
    254         for (length in 1..n) {
    255             var mex = ""
    256             var answer: String? = null
    257             fun recur() {
    258                 if (mex.length == length) {
    259                     if (mex !in s) {
    260                         answer = mex
    261                     }
    262                 } else {
    263                     for (chara in 'a'..'z') {
    264                         mex += chara
    265                         recur()
    266                         if (answer != null) {
    267                             return
    268                         }
    269                         mex = mex.substring(0 until mex.lastIndex)
    270                     }
    271                 }
    272             }
    273             recur()
    274             if (answer != null) {
    275                 println(answer)
    276                 break
    277             }
    278         }
    279     }
    280 }
    281 ```
    282 
    283 **Implementation in C++ by 1-gon**
    284 
    285 ```
    286 #include <bits/stdc++.h>
    287  
    288 #define ll long long
    289 #define sz(x) ((int) (x).size())
    290 #define all(x) (x).begin(), (x).end()
    291 #define fi first
    292 #define se second
    293 #define vi vector<int>
    294 #define pii pair<int, int>
    295 #define rep(i, a, b) for(int i = (a); i < (b); i++)
    296 using namespace std;
    297 template<typename T>
    298 using minpq = priority_queue<T, vector<T>, greater<T>>;
    299  
    300 void solve() {
    301     int n;
    302     string s;
    303     cin >> n >> s;
    304     set<string> se;
    305     rep(i, 0, n) {
    306         string ss;
    307         for(int k = 0; k < 5 && i + k < n; k++) {
    308             ss.push_back(s[i + k]);
    309             se.insert(ss);
    310         }
    311     }
    312     rep(len, 1, 6) {
    313         string t(len, 'a');
    314         while(true) {
    315             if(se.count(t) == 0) {
    316                 cout << t << '\n';
    317                 return;
    318             }
    319             int idx = len - 1;
    320             while(idx >= 0 && t[idx] == 'z') {
    321                 t[idx] = 'a';
    322                 idx--;
    323             }
    324             if(idx < 0) break;
    325             t[idx]++;
    326         }
    327     }
    328 }
    329 
    330 int main() {
    331     ios::sync_with_stdio(false);
    332     cin.tie(0);
    333     int te;
    334     cin >> te;
    335     while(te--) solve();
    336 }
    337 ```
    338 
    339 **Implementation in Haskell by Tlatoani**
    340 
    341 ```
    342 import Data.List (intercalate, tails, isPrefixOf, head)
    343 import Control.Monad (replicateM)
    344 import Data.Maybe (fromJust, listToMaybe, catMaybes)
    345 
    346 main = do t <- read <$> getLine
    347           replicateM t solve
    348 
    349 solve = do getLine
    350            s <- getLine
    351            putStrLn (leastNonSubstring s)
    352 
    353 leastNonSubstring s = head $ catMaybes [leastOfLength l | l <- [1..]]
    354   where leastOfLength l = helper "" l
    355         helper prefix 0 | isSubstring prefix s = Nothing
    356                         | otherwise            = Just prefix
    357         helper prefix l = listToMaybe $ catMaybes [helper (prefix ++ [letter]) (l - 1) | letter <- ['a'..'z']]
    358 
    359 isSubstring s t = any id (map (isPrefixOf s) (tails t))
    360 ```
    361 
    362 # [1536C - Diluc and Kaeya](/contest/1536/problem/C "Codeforces Round 724 (Div. 2)")
    363 
    364 Idea: [gotexans](/profile/gotexans "Master gotexans")
    365 
    366 Preparation: [gotexans](/profile/gotexans "Master gotexans")
    367 
    368 [Video editorial](https://www.youtube.com/watch?v=00TBpmgCwe4)
    369 
    370 **Hint 1**
    371 
    372 Turn into geometry problem
    373 
    374 **Hint 2**
    375 
    376 Represent every prefix as $(x, y)$ point in cartesian plane where $x$ = frequency of ‘D’ and $y$ = frequency of ‘K’. Draw a polyline connecting these points in order of increasing length of prefix.
    377 
    378 **Hint 3**
    379 
    380 Draw a line from origin to point. What can we say about intersections of poly-line with this line?
    381 
    382 **Solution**
    383 
    384 For each prefix, label it with a pair $(a, b)$ where $a$ = frequency of ‘D’ in this prefix and $b$ = frequency of ‘K’ in this prefix. Divide $a$ and $b$ by $gcd(a, b)$. If we iterate over all prefixes from to left, we can notice that the answer for the prefix equals the # of occurrences of this pair we have seen so far! This can be visualized by drawing a poly-line as mentioned in the hints.
    385 
    386 As for implementation, you can use a map in C++ or a HashMap in Java to achieve $O(n \log n)$ or $O(n)$ runtime.
    387 
    388 **Implementation in Java by hu_tao**
    389 
    390 ```
    391 //stan hu tao
    392 //come to K-expo!!!
    393 //watch me get carried in nct ridin
    394 import static java.lang.Math.max;
    395 import static java.lang.Math.min;
    396 import static java.lang.Math.abs;
    397 import static java.lang.System.out;
    398 import java.util.*;
    399 import java.io.*;
    400 import java.math.*;
    401 
    402 public class DilucKaeyaModel
    403 {
    404     public static void main(String hi[]) throws Exception
    405     {
    406         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
    407         StringTokenizer st = new StringTokenizer(infile.readLine());
    408         int T = Integer.parseInt(st.nextToken());
    409         StringBuilder sb = new StringBuilder();
    410         while(T-->0)
    411         {
    412             st = new StringTokenizer(infile.readLine());
    413             int N = Integer.parseInt(st.nextToken());
    414             char[] arr = infile.readLine().toCharArray();
    415             HashMap<String, Integer> map = new HashMap<String, Integer>();
    416             int dc = 0;
    417             int kc = 0;
    418             for(char c: arr)
    419             {
    420                 if(c == 'D')
    421                     dc++;
    422                 else
    423                     kc++;
    424                 int a = dc;
    425                 int b = kc;
    426                 if(a == 0)
    427                     b = 1;
    428                 else if(b == 0)
    429                     a = 1;
    430                 else
    431                 {
    432                     int gcd = gcd(a, b);
    433                     a /= gcd;   b /= gcd;
    434                 }
    435                 String key = a+":"+b;
    436                 push(map, key);
    437                 sb.append(map.get(key)+" ");
    438             }
    439             sb.append("\n");
    440         }
    441         System.out.print(sb);
    442     }
    443     public static int gcd(int a, int b)
    444     {
    445         if(a > b)
    446         {
    447             int t = a;
    448             a = b;
    449             b = t;
    450         }
    451         if(a == 0)
    452             return b;
    453         return gcd(b%a, a);
    454     }
    455     public static void push(HashMap<String, Integer> map, String k)
    456     {
    457         if(!map.containsKey(k))
    458             map.put(k, 1);
    459         else
    460             map.put(k, map.get(k)+1);
    461     }
    462 }
    463 ```
    464 
    465 **Implementation in Kotlin by Tlatoani**
    466 
    467 ```
    468 import java.util.*
    469 fun main() {
    470     repeat(readLine()!!.toInt()) {
    471         readLine()
    472         val freq = mutableMapOf<Pair<Int, Int>, Int>()
    473         var d = 0
    474         var k = 0
    475         val joiner = StringJoiner(" ")
    476         for (chara in readLine()!!) {
    477             when (chara) {
    478                 'D' -> d++
    479                 'K' -> k++
    480             }
    481             val g = gcd(d, k)
    482             val r = Pair(d / g, k / g)
    483             freq[r] = (freq[r] ?: 0) + 1
    484             joiner.add(freq[r]!!.toString())
    485         }
    486         println(joiner)
    487     }
    488 }
    489 
    490 fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
    491 ```
    492 
    493 **Implementation in C++ by smax**
    494 
    495 ```
    496 #include <bits/stdc++.h>
    497 using namespace std;
    498 
    499 #ifdef LOCAL
    500 #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
    501 #else
    502 #define DEBUG(...) 6
    503 #endif
    504 
    505 template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
    506 template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
    507 ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
    508 template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
    509 template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
    510 if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << s.substr(0, i) << " = " << x << " | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
    511 
    512 pair<int, int> getRatio(int a, int b) {
    513     int g = __gcd(a, b);
    514     a /= g;
    515     b /= g;
    516     return {a, b};
    517 }
    518 
    519 int main() {
    520     ios_base::sync_with_stdio(false);
    521     cin.tie(NULL);
    522 
    523     int t;
    524     cin >> t;
    525     while (t--) {
    526         int n;
    527         string s;
    528         cin >> n >> s;
    529 
    530         int d = 0, k = 0;
    531         map<pair<int, int>, int> mp;
    532         for (char c : s) {
    533             if (c == 'D') d++;
    534             else k++;
    535             cout << ++mp[getRatio(d, k)] << " ";
    536         }
    537         cout << "\n";
    538     }
    539 
    540     return 0;
    541 }
    542 ```
    543 
    544 **Implementation in Haskell by Tlatoani**
    545 
    546 ```
    547 import Data.List (intercalate)
    548 import Control.Monad (mapM, replicateM)
    549 import Data.Ratio ((%))
    550 import Data.Map (empty, findWithDefault, insert)
    551 
    552 main = do t <- read <$> getLine
    553           replicateM t solve
    554 
    555 solve = do getLine
    556            s <- getLine
    557            putStrLn (intercalate " " (map show (maxBlocks s)))
    558 
    559 maxBlocks s = helper s empty 0 0
    560   where helper "" _ _ _ = []
    561         helper (c:s) prev d k = x : helper s prev' d' k'
    562           where (d', k') | c == 'D' = (d + 1, k)
    563                          | c == 'K' = (d, k + 1)
    564                 r | k' == 0   = 69000000 % 1
    565                   | otherwise = d' % k'
    566                 x = (findWithDefault 0 r prev) + 1
    567                 prev' = insert r x prev
    568 ```
    569 
    570 # [1536D - Omkar and Medians](/contest/1536/problem/D "Codeforces Round 724 (Div. 2)")
    571 
    572 Idea: [rabaiBomkarBittalBang](/profile/rabaiBomkarBittalBang "Candidate Master rabaiBomkarBittalBang")
    573 
    574 Preparation: [rabaiBomkarBittalBang](/profile/rabaiBomkarBittalBang "Candidate Master rabaiBomkarBittalBang"), [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani")
    575 
    576 [Video editorial](https://www.youtube.com/watch?v=JyOFalVJaEc)
    577 
    578 **Solution**
    579 
    580 For some $k \lt n$, assume $b_1, b_2, \cdots, b_{k}$ is the *OmkArray* of some $a_1, a_2, \cdots, a_{2k-1}$, and we want to see what values of $a_{2k}, a_{2k+1}$ we can add so that $b_1, b_2, \cdots, b_{k+1}$ is the *OmkArray* of $a_1, a_2, \cdots, a_{2k+1}$. Let $c_1, c_2, \cdots, c_{2k-1}$ be $a_1, a_2, \cdots, a_{2k-1}$ sorted in ascending order.
    581 
    582 If $b_{k+1} \geq b_k$, note that $b_{k} = c_k$ and there are $k-2$ elements of $a$ $\geq c_{k+1}$, so no matter how large $a_{2k}, a_{2k+1}$ are there will be at most $k$ elements larger than $c_{k+1}$ in $a_1, a_2, \cdots, a_{2k+1}$. This gives $b_{k+1} \leq c_{k+1}$. We can use a similar argument to show $b_{k+1} \geq c_{k-1}$. Now we want to bound $c_{k+1}$ and $c_{k-1}$. Note that each distinct value among $b_1, b_2, \cdots, b_k$ must appear at least once in $a_1, a_2, \cdots, a_{2k-1}$. Therefore, if $i$, $j$ satisfy that $b_i$ is the largest value of $b_i\leq b_k$ and $i \neq k$, and $b_j$ is the smallest value of $b_j \geq b_k$, $j \neq k$, then we have $c_{k+1} \leq b_j$, $c_{k-1} \geq b_i$, and so $b_i \leq b_{k+1} \leq b_j$. If no such largest/smallest values exist, then we can assume $b_{k+1}$ is not bounded above/below.
    583 
    584 Therefore, if $b$ has an *OmkArray*, it is necessary that for all $i$, there does not exist a $j\leq i$ such that $b_j$ is between $b_i$ and $b_{i+1}$, exclusive. I claim this is also sufficient. We can construct such an array $a$ using the following algorithm:
    585 
    586 * Let $a_1 = b_1$.
    587 * If $b_{i+1}=b_j$ for some $b_j \lt b_i$ with $j \lt i$, let $a_{2k-2}, a_{2k-1} = -\infty$ (we can replace $-\infty$ with some sufficiently small constant at the end of our array creation process).
    588 * Otherwise, if $b_{i+1} \lt b_i$ then let $a_{2k-2} = -\infty$, $a_{2k-1} = b_{i+1}$.
    589 * If $b_{i+1}=b_j$ for some $b_j \gt b_i$ with $j \lt i$, let $a_{2k-2}, a_{2k-1} = \infty$ (we can replace $\infty$ with some sufficiently large constant at the end of our array creation process).
    590 * Otherwise, if $b_{i+1} \gt b_i$ then let $a_{2k-2} = \infty$, $a_{2k-1} = b_{i+1}$.
    591 * Finally, if $b_{i+1} = b_i$, let $a_{2k-2} = -\infty$, $a_{2k-1} = \infty$.
    592 
    593 This means that an equivalent condition to having an *OmkArray* is for all $i$, there does not exist a $j\leq i$ such that $b_j$ is between $b_i$ and $b_{i+1}$, exclusive. There are multiple ways to check this for an array $b$, but one clean way would be to keep some TreeSet $s$, and check if $b_{i+1}$ is between \t{s.ceil($b_i$)} and \t{s.floor($b_i$)} for all $i$, and then adding $b_{i+1}$ to $s$ if it is not already added.
    594 
    595 **Linear time implementation in Java by rabaiBomkarBittalBang**
    596 
    597 ```
    598 //Praise our lord and saviour qlf9
    599 import java.util.*;
    600 import java.io.*;
    601 import java.math.*;
    602 import java.text.*;
    603 public class C{
    604 public static void main(String[] omkar) throws Exception
    605 {
    606    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    607    StringTokenizer st = new StringTokenizer(in.readLine());
    608    StringBuilder sb = new StringBuilder();
    609    int cases = Integer.parseInt(st.nextToken());
    610    for(int i = 0; i < cases; i++)
    611    {
    612       solve(in, st, sb);
    613    }  
    614    System.out.print(sb);
    615         }
    616  public static void solve(BufferedReader in, StringTokenizer st, StringBuilder sb) throws Exception
    617  {
    618    int n = Integer.parseInt(in.readLine());
    619    int[] arr = readArr(n, in, st);
    620    Node currNode = new Node(arr[0]);
    621    int currVal;
    622    Node temp;
    623    for(int i = 1; i < n; i++)
    624    {
    625       currVal = arr[i];
    626       if(currVal < currNode.value)
    627       {
    628          if(currNode.prev != null && currVal < currNode.prev.value)
    629          {
    630             sb.append("NO\n");
    631             return;
    632          }
    633          if(currNode.prev == null || currNode.prev.value < currVal)
    634          {
    635             temp = new Node(currVal);
    636             temp.prev = currNode.prev;
    637             temp.next = currNode;
    638             if(currNode.prev != null)
    639             {
    640                currNode.prev.next = temp;
    641             }
    642             currNode.prev = temp;
    643             currNode = temp;
    644          }
    645          else
    646          {
    647             currNode = currNode.prev;
    648          }
    649       }
    650       else if(currVal > currNode.value)
    651       {
    652          if(currNode.next != null && currVal > currNode.next.value)
    653          {
    654             sb.append("NO\n");
    655             return;
    656          }
    657          if(currNode.next == null || currNode.next.value > currVal)
    658          {
    659             temp = new Node(currVal);
    660             temp.next = currNode.next;
    661             temp.prev = currNode;
    662             if(currNode.next != null)
    663             {
    664                currNode.next.prev = temp;
    665             }
    666             currNode.next = temp;
    667             currNode = temp;
    668          }
    669          else
    670          {
    671             currNode = currNode.next;
    672          }
    673       }
    674    }
    675    sb.append("YES\n");
    676  }
    677  public static int[] readArr(int N, BufferedReader in, StringTokenizer st) throws Exception
    678  {
    679     int[] arr = new int[N];
    680     st = new StringTokenizer(in.readLine());
    681     for(int i=0; i < N; i++)
    682     arr[i] = Integer.parseInt(st.nextToken());
    683     return arr;
    684  }
    685  static class Node
    686  {
    687    int value;
    688    Node prev;
    689    Node next;
    690    public Node(int v)
    691    {
    692       value = v;
    693       prev = null;
    694       next = null;
    695    }
    696  }
    697 }
    698 ```
    699 
    700 **Implementation in Kotlin by Tlatoani**
    701 
    702 ```
    703 import java.io.BufferedReader
    704 import java.io.InputStreamReader
    705 import java.util.*
    706 
    707 fun main() {
    708     val jin = BufferedReader(InputStreamReader(System.`in`))
    709     val out = StringBuilder()
    710     for (c in 1..jin.readLine().toInt()) {
    711         val n = jin.readLine().toInt()
    712         val tokenizer = StringTokenizer(jin.readLine())
    713         var mid = tokenizer.nextToken().toInt()
    714         val treeSet = TreeSet<Int>()
    715         treeSet.add(Int.MIN_VALUE)
    716         treeSet.add(mid)
    717         treeSet.add(Int.MAX_VALUE)
    718         var answer = true
    719         for (j in 2..n) {
    720             val next = tokenizer.nextToken().toInt()
    721             if (next < treeSet.lower(mid)!! || next > treeSet.higher(mid)!!) {
    722                 answer = false
    723                 break
    724             }
    725             mid = next
    726             treeSet.add(mid)
    727         }
    728         out.appendln(if (answer) "yEs" else "nO")
    729     }
    730     print(out)
    731 }
    732 ```
    733 
    734 **Implementation in C++ by kefaa2**
    735 
    736 ```
    737 #ifdef DEBUG
    738 #define _GLIBCXX_DEBUG
    739 #endif
    740 #pragma GCC optimize("O3")
    741 #include <bits/stdc++.h>
    742 
    743 using namespace std;
    744 typedef long double ld;
    745 typedef long long ll;
    746 int n;
    747 const int maxN = 2e5 + 10;
    748 int a[maxN];
    749 
    750 int main() {
    751     ios_base::sync_with_stdio(false);
    752     cin.tie(nullptr);
    753 //    freopen("input.txt", "r", stdin);
    754     int tst;
    755     cin >> tst;
    756     while (tst--) {
    757         int n;
    758         cin >> n;
    759         for (int i = 1; i <= n; i++) {
    760             cin >> a[i];
    761         }
    762         set<int> s;
    763         s.insert(a[1]);
    764         bool ok = true;
    765         for (int i = 2; i <= n; i++) {
    766             int prv = a[i - 1];
    767             if (prv != a[i]) {
    768                 if (prv < a[i]) {
    769                     auto it = s.upper_bound(prv);
    770                     if (it != s.end() && (*it < a[i])) {
    771                         ok = false;
    772                         break;
    773                     }
    774                 }
    775                 if (prv > a[i]) {
    776                     auto it = s.lower_bound(prv);
    777                     if (it != s.begin() && (*(--it) > a[i])) {
    778                         ok = false;
    779                         break;
    780                     }
    781                 }
    782             }
    783             s.insert(a[i]);
    784         }
    785         if (ok) cout << "YES\n";
    786         else cout << "NO\n";
    787     }
    788     return 0;
    789 }
    790 ```
    791 
    792 **Implementation in Haskell by Tlatoani**
    793 
    794 ```
    795 import Data.List (intercalate)
    796 import Data.Set (singleton, lookupLT, lookupGT, insert)
    797 import Control.Monad (mapM, replicateM)
    798 
    799 main = do t <- read <$> getLine
    800           replicateM t solve
    801 
    802 solve = do getLine
    803            xs <- (map read . words) <$> getLine
    804            putStrLn (if isOmkArray xs then "yEs" else "nO")
    805 
    806 isOmkArray :: [Int] -> Bool
    807 isOmkArray (x:xs) = helper xs x (singleton x)
    808   where helper [] _ _ = True
    809         helper (x:xs) prev allPrev | maybe False (x <) (lookupLT prev allPrev) || maybe False (x >) (lookupGT prev allPrev) = False
    810                                    | otherwise                                                                              = helper xs x (insert x allPrev)
    811 ```
    812 
    813 # [1536E - Omkar and Forest](/contest/1536/problem/E "Codeforces Round 724 (Div. 2)")
    814 
    815 Idea: [gotexans](/profile/gotexans "Master gotexans")
    816 
    817 Preparation: [gotexans](/profile/gotexans "Master gotexans")
    818 
    819 [Video editorial](https://www.youtube.com/watch?v=cqzBCjXIUwA)
    820 
    821 **Hint 1**
    822 
    823 Consider forcing some set of ‘#’ positions to be $0$ and the rest to be positive integers.
    824 
    825 **Hint 2**
    826 
    827 Multisource BFS
    828 
    829 **Solution**
    830 
    831 Imagine picking some subset of ‘#’ and making them $0$. Then there is exactly one way to make all the remaining ‘#’ positive integers. To see why, imagine multisource BFS with all $0$ as the sources. After the BFS, each ‘#’ will be equal to the minimum distance from itself to any $0$ cell. Difference between adjacent cells will be at most $1$. Proof can be shown by contradiction: if two cells with difference $\geq 2$ existed, then the larger of these cells is not labeled with the shortest distance to a source (since the distance from the smaller cell $+ 1$ will be a better choice). Because of the nature of BFS, we can also ensure the second condition is also satisfied, since the only cells that have no neighbor strictly smaller will be the source cells. This is the only valid assignment because if we make any number larger, there will exist a pair of cells with difference $\geq 2$. If we try to make any number smaller, there will exist a cell with positive karma that has no strictly smaller neighbor.
    832 
    833 If we let $k$ equal to the frequency of ‘#’ in the input, then the answer is $2^k$. Keep in mind of the special case where the input is all ‘#’, in which case you have to subtract $1$. This is because a possible arrangement must contain at least one cell with karma of $0$.
    834 
    835 Obviously the solution runs in $O(nm)$ time.
    836 
    837 **Implementation in Java by hu_tao**
    838 
    839 ```
    840 //Model Solution 2, uses fast expo
    841 import static java.lang.Math.max;
    842 import static java.lang.Math.min;
    843 import static java.lang.Math.abs;
    844 import static java.lang.System.out;
    845 import java.util.*;
    846 import java.io.*;
    847 import java.math.*;
    848 
    849 public class OmkarAndForestModel2
    850 {
    851     static final long MOD = 1000000007L;
    852     public static void main(String hi[]) throws Exception
    853     {
    854         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
    855         StringTokenizer st = new StringTokenizer(infile.readLine());
    856         int T = Integer.parseInt(st.nextToken());
    857         StringBuilder sb = new StringBuilder();
    858         while(T-->0)
    859         {
    860             st = new StringTokenizer(infile.readLine());
    861             int N = Integer.parseInt(st.nextToken());
    862             int M = Integer.parseInt(st.nextToken());
    863             int cnt = 0;
    864             for(int i=0; i < N; i++)
    865             {
    866                 String row = infile.readLine();
    867                 for(char c: row.toCharArray())
    868                     if(c == '#')
    869                         cnt++;
    870             }
    871             long res = power(2, cnt, MOD);
    872             if(cnt == N*M)
    873                 res = (res-1+MOD)%MOD;
    874             sb.append(res+"\n");
    875         }
    876         System.out.print(sb);
    877     }
    878     public static long power(long x, long y, long p)
    879     {
    880         //0^0 = 1
    881         long res = 1L;
    882         x = x%p;
    883         while(y > 0)
    884         {
    885             if((y&1)==1)
    886                 res = (res*x)%p;
    887             y >>= 1;
    888             x = (x*x)%p;
    889         }
    890         return res;
    891     }
    892 }
    893 ```
    894 
    895 **Implementation in Kotlin by Tlatoani**
    896 
    897 ```
    898 const val MOD = 1000000007L
    899 
    900 fun main() {
    901     for (c in 1..readLine()!!.toInt()) {
    902         val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    903         var zeros = (1..n).sumBy{ readLine()!!.count { it == '0' } }
    904         var answer = 1L
    905         for (j in 1..(n * m) - zeros) {
    906             answer *= 2L
    907             answer %= MOD
    908         }
    909         if (zeros == 0) {
    910             answer--
    911         }
    912         println(answer)
    913     }
    914 }
    915 ```
    916 
    917 **Implementation in C++ by kefaa2**
    918 
    919 ```
    920 #ifdef DEBUG
    921 #define _GLIBCXX_DEBUG
    922 #endif
    923 #pragma GCC optimize("O3")
    924 #include <bits/stdc++.h>
    925 
    926 using namespace std;
    927 typedef long double ld;
    928 typedef long long ll;
    929 const int mod = (int)1e9 + 7;
    930 int main() {
    931     ios_base::sync_with_stdio(false);
    932     cin.tie(nullptr);
    933 //    freopen("input.txt", "r", stdin);
    934     int tst;
    935     cin >> tst;
    936     while (tst--) {
    937         int n, m;
    938         cin >> n >> m;
    939         int ans = 1;
    940         bool has =false;
    941         for (int i = 0; i < n; i++) {
    942             for (int j = 0; j < m; j++) {
    943                 char c;
    944                 cin >> c;
    945                 if (c == '0') {
    946                     has = true;
    947                 }
    948                 else {
    949                     ans = (2LL * ans) % mod;
    950                 }
    951             }
    952         }
    953         if (has) {
    954             cout << ans << '\n';
    955         }
    956         else {
    957             cout << (ans - 1) << '\n';
    958         }
    959     }
    960     return 0;
    961 }
    962 ```
    963 
    964 **Implementation in Haskell by Tlatoani**
    965 
    966 ```
    967 import Data.List (intercalate)
    968 import Control.Monad (replicateM)
    969 
    970 md x = mod x 1000000007
    971 
    972 main = do t <- read <$> getLine
    973           replicateM t solve
    974 
    975 solve = do n:m:[] <- (map read . words) <$> getLine
    976            free <- (sum . map (sum . map (\chara -> if chara == '#' then 1 else 0))) <$> replicateM n getLine
    977            putStrLn $ show (if free == n * m then pow 2 free - 1 else pow 2 free)
    978 
    979 pow :: (Integral a) => Integer -> a -> Integer
    980 pow _ 0 = 1
    981 pow x y = md $ x * (pow x (y - 1))
    982 ```
    983 
    984 # [1536F - Omkar and Akmar](/contest/1536/problem/F "Codeforces Round 724 (Div. 2)")
    985 
    986 Idea: [malachi_toney_goat](/profile/malachi_toney_goat "Master malachi_toney_goat")
    987 
    988 Preparation: [malachi_toney_goat](/profile/malachi_toney_goat "Master malachi_toney_goat")
    989 
    990 [Video editorial](https://www.youtube.com/watch?v=iTou7R_fJfY)
    991 
    992 **Hint 1**
    993 
    994 Solve a simpler version of the problem, where you just need to print who would win if both players play optimally.
    995 
    996 **Hint 1 Hint**
    997 
    998 Consider the possible ending states of the board.
    999 
   1000 **Hint 1 Solution**
   1001 
   1002 The 2nd player, Omkar, always wins no matter what either player does. The easiest way to see this is by considering ending states of the board. An ending state with an even number of letters means that the 2nd player wins (because the first player is the next player and there are no more moves), and an ending state with an odd number of letters means that the 1st player wins.
   1003 
   1004 An ending state must be in the form ABABA... or BABA..., where there are 0 or 1 empty cells in between each letter and the letters form an alternating pattern. If there is more than 1 empty cell in between two cells, then a player will be able to play a letter, thus it is not a valid ending state.
   1005 
   1006 If an ending state has two of the same letters next to each other, then it is not a valid ending state. Either they are next to each other, which is illegal, or there is at least one empty cell in between them, which means that a player can play the other letter in between.
   1007 
   1008 Since the ending state must form an alternating pattern, there must be an even number of states. Thus, the 2nd player, Omkar, always wins.
   1009 
   1010 **Hint 2**
   1011 
   1012 Find the implication of the 2nd player always winning on the number of optimal games.
   1013 
   1014 **Hint 2 Solution**
   1015 
   1016 Because the 2nd player always wins no matter what, the number of optimal games basically means the total number of possible games.
   1017 
   1018 **Solution**
   1019 
   1020 Because of Hint 1 and Hint 2, we want to find the total number of possible games. This can be done by iterating over the number of moves and counting the number of ways to play a game with that number of moves.
   1021 
   1022 We want to find the number of games that end in $x$ moves on a board of size $n$.
   1023 
   1024 The first step is to calculate the total number of ending states. If $x=n$, the total number of ending states is just $2$ because you can either have ABABA... or BABAB...
   1025 
   1026 Otherwise, a game that ends in $x$ moves will consist of $x$ letters, for example A|B|A|B|... where a | is a possible location of a single empty cell (there cannot be multiple empty cells next to each other or else it would not be a valid ending state). There are $x$ possible places where there can be an empty cell, and $n-x$ empty cells, so there are $\binom x {n-x}$ ways to choose places to put empty cells. Due to the circular nature of the board, you need to account for the case where the first cell on the board is an empty cell (the previous formula only works if the first cell is not empty). If you set the first cell to be empty, there are not $x-1$ possible places to put an empty cell and $n-x-1$ remaining empty cells, so you have to add $\binom {x-1} {n-x-1}$. Multiply the answer by $2$ to account for starting with an A or B.
   1027 
   1028 Finally, multiply by $x!$ to account for all the ways you can reach each ending configuration.
   1029 
   1030 Thus, if $x=n$, there are $2 \cdot x!$ optimal games, otherwise there are $2 \cdot (\binom x {n-x} + \binom {x-1} {n-x-1} ) \cdot x!$ optimal games.
   1031 
   1032 Add up the number of games that end in $x$ moves for all even $x$ from $\lceil \frac{n}{2} \rceil$ to $n$, inclusive. Thus, the solution is $O(n)$.
   1033 
   1034 **Implementation in Java by golions**
   1035 
   1036 ```
   1037 //make sure to make new file!
   1038 import java.io.*;
   1039 import java.util.*;
   1040 
   1041 public class OmkarAndAkmarSolution{
   1042    
   1043    public static int MAXN = 1000005;
   1044    public static long MOD = 1000000007L;
   1045    public static long[] fac;
   1046    public static long[] ifac;
   1047    
   1048    public static void main(String[] args)throws IOException{
   1049       BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
   1050       PrintWriter out = new PrintWriter(System.out);
   1051       
   1052       int n = Integer.parseInt(f.readLine());
   1053       
   1054       fac = new long[MAXN];
   1055       ifac = new long[MAXN];
   1056       
   1057       fac[0] = 1L;
   1058       ifac[0] = 1L;
   1059       for(int k = 1; k < MAXN; k++){
   1060          fac[k] = (fac[k-1] * (long)k + MOD)%MOD;
   1061          ifac[k] = modInverse(fac[k],MOD);
   1062       }
   1063       
   1064       /*
   1065       ifac[MAXN-1] = modInverse(fac[MAXN-1],MOD);
   1066       for(int k = MAXN-2; k >= 0; k--){
   1067          ifac[k] = (ifac[k+1]*(long)(k+1) + MOD)%MOD;
   1068       }*/
   1069       
   1070       int start = (n+1)/2;
   1071       if(start % 2 == 1) start++;
   1072       
   1073       long answer = 0L;
   1074       for(int k = start; k <= n; k+=2){
   1075          long prod1 = 1L;
   1076          if(n-k>=1){
   1077             //doesn't do first skip
   1078             prod1 = choose(k,n-k);
   1079             //does first skip
   1080             prod1 = (prod1 + choose(k-1,n-k-1) + MOD)%MOD;
   1081          }
   1082          long prod2 = (prod1*2L + MOD)%MOD;
   1083          long prod3 = (prod2*fac[k] + MOD)%MOD;
   1084          answer = (answer + prod3 + MOD)%MOD;
   1085       }
   1086       
   1087       out.println(answer);
   1088       
   1089       
   1090       
   1091       
   1092       
   1093       
   1094       
   1095       
   1096       out.close();
   1097    }
   1098    
   1099    //a choose b, a!/(b!(a-b)!)
   1100    public static long choose(int a, int b){
   1101       long prod = (fac[a]*ifac[b] + MOD)%MOD;
   1102       long prod2 = (prod*ifac[a-b] + MOD)%MOD;
   1103       return prod2;
   1104    }
   1105    
   1106    public static long modInverse(long a, long m)
   1107     {
   1108         long m0 = m;
   1109         long y = 0;
   1110         long x = 1;
   1111         if (m == 1)
   1112             return 0;
   1113  
   1114         while (a > 1) {
   1115             // q is quotient
   1116             long q = a / m;
   1117  
   1118             long t = m;
   1119  
   1120             // m is remainder now, process
   1121             // same as Euclid's algo
   1122             m = a % m;
   1123             a = t;
   1124             t = y;
   1125  
   1126             // Update x and y
   1127             y = x - q * y;
   1128             x = t;
   1129         }
   1130  
   1131         // Make x positive
   1132         if (x < 0)
   1133             x += m0;
   1134  
   1135         return x;
   1136     }
   1137    
   1138       
   1139 }
   1140 ```
   1141 
   1142 **Implementation in Kotlin by Tlatoani**
   1143 
   1144 ```
   1145 const val MOD = 1000000007L
   1146 
   1147 fun main() {
   1148     val n = readLine()!!.toInt()
   1149     val factorial = LongArray(n + 1)
   1150     factorial[0] = 1L
   1151     for (j in 1..n) {
   1152         factorial[j] = (j.toLong() * factorial[j - 1]) % MOD
   1153     }
   1154     val invFactorial = LongArray(n + 1)
   1155     invFactorial[n] = factorial[n] pow -1
   1156     for (j in n - 1 downTo 0) {
   1157         invFactorial[j] = ((j + 1).toLong() * invFactorial[j + 1]) % MOD
   1158     }
   1159     fun choose(a: Int, b: Int) = if (b in 0..a) ((factorial[a] * ((invFactorial[b] * invFactorial[a - b]) % MOD)) % MOD) else 0L
   1160     var answer = 0L
   1161     for (k in 0..n step 2) {
   1162         answer += factorial[k] * (choose(k, n - k) + choose(k - 1, n - k - 1))
   1163         answer %= MOD
   1164     }
   1165     answer *= 2L
   1166     answer %= MOD
   1167     println(answer)
   1168 }
   1169 
   1170 const val MOD_TOTIENT = MOD.toInt() - 1
   1171 
   1172 infix fun Long.pow(power: Int): Long {
   1173     var e = power
   1174     e %= MOD_TOTIENT
   1175     if (e < 0) {
   1176         e += MOD_TOTIENT
   1177     }
   1178     if (e == 0 && this == 0L) {
   1179         return this
   1180     }
   1181     var b = this % MOD
   1182     var res = 1L
   1183     while (e > 0) {
   1184         if (e and 1 != 0) {
   1185             res *= b
   1186             res %= MOD
   1187         }
   1188         b *= b
   1189         b %= MOD
   1190         e = e shr 1
   1191     }
   1192     return res
   1193 }
   1194 ```
   1195 
   1196 **Implementation in C++ by kefaa2**
   1197 
   1198 ```
   1199 #ifdef DEBUG
   1200 #define _GLIBCXX_DEBUG
   1201 #endif
   1202 #pragma GCC optimize("O3")
   1203 #include <bits/stdc++.h>
   1204 
   1205 using namespace std;
   1206 typedef long double ld;
   1207 typedef long long ll;
   1208 const int mod = (int)1e9 + 7;
   1209 int mult(int a, int b) {
   1210     return (1LL * a * b) % mod;
   1211 }
   1212 int sum(int a, int b) {
   1213     int s = a + b;
   1214     if (s >= mod) s -= mod;
   1215     return s;
   1216 }
   1217 const int maxN = 2e6 + 10;
   1218 int inv[maxN], fact[maxN], invfact[maxN];
   1219 int cnk(int n, int k) {
   1220     if (n < k || k < 0) return 0;
   1221     return mult(fact[n], mult(invfact[k], invfact[n - k]));
   1222 }
   1223 int main() {
   1224     ios_base::sync_with_stdio(false);
   1225     cin.tie(nullptr);
   1226 //    freopen("input.txt", "r", stdin);
   1227     inv[1] = 1;
   1228     fact[0] = invfact[0] = fact[1] = invfact[1] = 1;
   1229     for (int i = 2; i < maxN; i++) {
   1230         inv[i] = mult(inv[mod % i], mod - mod / i);
   1231         fact[i] = mult(fact[i - 1], i);
   1232         invfact[i] = mult(invfact[i - 1], inv[i]);
   1233     }
   1234     int ans = 0;
   1235     int n;
   1236     cin >> n;
   1237     for (int moves = 0; moves <= n - 1; moves++) {
   1238         int spaces = n - 1 - moves;
   1239         int coef = cnk(moves + 1, spaces);
   1240         if (moves % 2 == 0) continue;
   1241         int fi = (moves + 1) / 2;
   1242         coef = mult(coef, fact[moves]);
   1243      //   cout << coef << endl;
   1244         ans = sum(ans, coef);
   1245     }
   1246     ans = mult(ans, 2 * n);
   1247     cout << ans;
   1248     return 0;
   1249 }
   1250 ```
   1251 
   1252 **Implementation in Haskell by Tlatoani**
   1253 
   1254 ```
   1255 import Data.List (reverse)
   1256 import Data.Array (listArray, (!))
   1257 
   1258 chara = 1000000007
   1259 md x = mod x chara
   1260 
   1261 main = do n <- read <$> getLine
   1262           putStrLn $ show (solve n)
   1263 
   1264 solve n = md $ 2 * (sum (map (\k -> md (factorials!k * (choose k (n - k) + choose (k - 1) (n - k - 1)))) [0,2..n]))
   1265   where factorials = listArray (0, n) (reverse (helper n))
   1266           where helper 0 = 1:[]
   1267                 helper n' = md (n' * f):fs
   1268                   where fs@(f:_) = helper (n' - 1)
   1269         invFactorials = listArray (0, n) (helper 0)
   1270           where helper n' | n' == n   = inv (factorials!n):[]
   1271                           | otherwise = md ((n' + 1) * f):fs
   1272                   where fs@(f:_) = helper (n' + 1)
   1273         choose a b | 0 <= b && b <= a = md $ factorials!a * (md (invFactorials!b * invFactorials!(a - b)))
   1274                    | otherwise        = 0
   1275 
   1276 modPow :: (Integral a) => Integer -> a -> Integer
   1277 modPow _ 0 = 1
   1278 modPow x y = md $ (if even y then 1 else x) * modPow (md (x * x)) (div y 2)
   1279 
   1280 inv x = modPow x (chara - 2)
   1281 ```