**Adiv2**

To solve the problem one could just store two arrays <span class="tex-span"><i>hused</i>[<i>j</i>]</span> and <span class="tex-span"><i>vused</i>[<i>j</i>]</span> sized <span class="tex-span"><i>n</i></span> and filled with false initially. Then process intersections one by one from <span class="tex-span">1</span> to <span class="tex-span"><i>n</i></span>, and if for <span class="tex-span"><i>i</i></span>-th intersections both <span class="tex-span"><i>hused</i>[<i>h</i><sub class="lower-index"><i>i</i></sub>]</span> and <span class="tex-span"><i>vused</i>[<i>v</i><sub class="lower-index"><i>i</i></sub>]</span> are false, add <span class="tex-span"><i>i</i></span> to answer and set both <span class="tex-span"><i>hused</i>[<i>h</i><sub class="lower-index"><i>i</i></sub>]</span> and <span class="tex-span"><i>vused</i>[<i>v</i><sub class="lower-index"><i>i</i></sub>]</span> with true meaning that <span class="tex-span"><i>h</i><sub class="lower-index"><i>i</i></sub></span>-th horizontal and <span class="tex-span"><i>v</i><sub class="lower-index"><i>i</i></sub></span>-th vertical roads are now asphalted, and skip asphalting the intersection roads otherwise.

Such solution has <span class="tex-span"><i>O</i>(<i>n</i><sup class="upper-index">2</sup>)</span> complexity.

**Bdiv2**

It is always optimal to pass all the computers in the row, starting from <span class="tex-span">1</span>-st to <span class="tex-span"><i>n</i></span>-th, then from <span class="tex-span"><i>n</i></span>-th to first, then again from first to <span class="tex-span"><i>n</i></span>-th, etc. and collecting the information parts as possible, while not all of them are collected. 

Such way gives robot maximal use of every direction change. <span class="tex-span"><i>O</i>(<i>n</i><sup class="upper-index">2</sup>)</span> solution using this approach must have been passed system tests.

**Adiv1**

Let the answer be <span class="tex-span"><i>a</i><sub class="lower-index">1</sub> ≤ <i>a</i><sub class="lower-index">2</sub> ≤ ... ≤ <i>a</i><sub class="lower-index"><i>n</i></sub></span>. We will use the fact that <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>i</i></sub>, <i>a</i><sub class="lower-index"><i>j</i></sub>) ≤ <i>a</i><sub class="lower-index"><i>min</i>(<i>i</i>, <i>j</i>)</sub></span>. 

It is true that <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>n</i></sub>, <i>a</i><sub class="lower-index"><i>n</i></sub>) = <i>a</i><sub class="lower-index"><i>n</i></sub> ≥ <i>a</i><sub class="lower-index"><i>i</i></sub> ≥ <i>gcd</i>(<i>a</i><sub class="lower-index"><i>i</i></sub>, <i>a</i><sub class="lower-index"><i>j</i></sub>)</span> for every <span class="tex-span">1 ≤ <i>i</i>, <i>j</i> ≤ <i>n</i></span>. That means that <span class="tex-span"><i>a</i><sub class="lower-index"><i>n</i></sub></span> is equal to maximum element in the table. Let set <span class="tex-span"><i>a</i><sub class="lower-index"><i>n</i></sub></span> to maximal element in the table and delete it from table elements set. We've deleted <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>n</i></sub>, <i>a</i><sub class="lower-index"><i>n</i></sub>)</span>, so the set now contains all <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>i</i></sub>, <i>a</i><sub class="lower-index"><i>j</i></sub>)</span>, for every <span class="tex-span">1 ≤ <i>i</i>, <i>j</i> ≤ <i>n</i></span> and <span class="tex-span">1 ≤ <i>min</i>(<i>i</i>, <i>j</i>) ≤ <i>n</i> - 1</span>. 

By the last two inequalities <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>i</i></sub>, <i>a</i><sub class="lower-index"><i>j</i></sub>) ≤ <i>a</i><sub class="lower-index"><i>min</i>(<i>i</i>, <i>j</i>)</sub> ≤ <i>a</i><sub class="lower-index"><i>n</i> - 1</sub> = <i>gcd</i>(<i>a</i><sub class="lower-index"><i>n</i> - 1</sub>, <i>a</i><sub class="lower-index"><i>n</i> - 1</sub>)</span>. As soon as set contains <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>n</i> - 1</sub>, <i>a</i><sub class="lower-index"><i>n</i> - 1</sub>)</span>, the maximum element in current element set is equal to <span class="tex-span"><i>a</i><sub class="lower-index"><i>n</i> - 1</sub></span>. As far as we already know <span class="tex-span"><i>a</i><sub class="lower-index"><i>n</i></sub></span>, let's delete the <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>n</i> - 1</sub>, <i>a</i><sub class="lower-index"><i>n</i> - 1</sub>)</span>, <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>n</i> - 1</sub>, <i>a</i><sub class="lower-index"><i>n</i></sub>)</span>, <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>n</i></sub>, <i>a</i><sub class="lower-index"><i>n</i> - 1</sub>)</span> from the element set. Now set contains all the <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>i</i></sub>, <i>a</i><sub class="lower-index"><i>j</i></sub>)</span>, for every <span class="tex-span">1 ≤ <i>i</i>, <i>j</i> ≤ <i>n</i></span> and <span class="tex-span">1 ≤ <i>min</i>(<i>i</i>, <i>j</i>) ≤ <i>n</i> - 2</span>.

We're repeating that operation for every <span class="tex-span"><i>k</i></span> from <span class="tex-span"><i>n</i> - 2</span> to <span class="tex-span">1</span>, setting <span class="tex-span"><i>a</i><sub class="lower-index"><i>k</i></sub></span> to maximum element in the set and deleting the <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>k</i></sub>, <i>a</i><sub class="lower-index"><i>k</i></sub>)</span>, <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>i</i></sub>, <i>a</i><sub class="lower-index"><i>k</i></sub>)</span>, <span class="tex-span"><i>gcd</i>(<i>a</i><sub class="lower-index"><i>k</i></sub>, <i>a</i><sub class="lower-index"><i>i</i></sub>)</span> for every <span class="tex-span"><i>k</i> &lt; <i>i</i> ≤ <i>n</i></span> from the set.

One could prove correctness of this algorithm by mathematical induction. For performing deleting and getting maximum element operations one could use multiset or map structure, so solution has complexity <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b4ca8bf08d5a9465b6c031484892b4a5987266a4.png" style="max-width: 100.0%;max-height: 100.0%;" />.

**Bdiv1**

One could calculate matrix sized <span class="tex-span"><i>n</i> × <i>n</i></span> <span class="tex-span"><i>mt</i>[<i>i</i>][<i>j</i>]</span> &mdash; the length of the longest non-decreasing subsequence in array <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index"><i>n</i></sub></span>, starting at element, greater-or-equal to <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> and ending strictly in <span class="tex-span"><i>a</i><sub class="lower-index"><i>j</i></sub></span> element with <span class="tex-span"><i>j</i></span>-th index.

One could prove that if we have two matrices sized <span class="tex-span"><i>n</i> × <i>n</i></span> <span class="tex-span"><i>A</i>[<i>i</i>][<i>j</i>]</span> (the answer for <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index"><i>pn</i></sub></span> starting at element, greater-or-equal to <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> and ending strictly in <span class="tex-span"><i>a</i><sub class="lower-index"><i>j</i></sub></span> element with <span class="tex-span"><i>j</i></span>-th index inside last block (<span class="tex-span"><i>a</i><sub class="lower-index">(<i>p</i> - 1)<i>n</i> + 1</sub>, ..., <i>a</i><sub class="lower-index"><i>pn</i></sub></span>) and <span class="tex-span"><i>B</i>[<i>i</i>][<i>j</i>]</span> (the answer for <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index"><i>qn</i></sub></span> \ldots), then the multiplication of this matrices in a way

<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/ec76ef861e266fbeef62160592455a681ec9d29f.png" style="max-width: 100.0%;max-height: 100.0%;" />

will give the same matrix but for length <span class="tex-span"><i>p</i> + <i>q</i></span>. As soon as such multiplication is associative, next we will use fast matrix exponentiation algorithm to calculate <span class="tex-span"><i>M</i>[<i>i</i>][<i>j</i>]</span> (the answer for <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index"><i>nT</i></sub></span>) &mdash; matrix <span class="tex-span"><i>mt</i>[<i>i</i>][<i>j</i>]</span> raised in power <span class="tex-span"><i>T</i></span>. The answer is the maximum in matrix <span class="tex-span"><i>M</i></span>. Such solution has complexity <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/a79fb2bad2fcbb7084eacb100432430903b4fad0.png" style="max-width: 100.0%;max-height: 100.0%;" />.

There's an alternative solution. As soon as <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, <i>a</i><sub class="lower-index">2</sub>, ..., <i>a</i><sub class="lower-index"><i>nT</i></sub></span> contains maximum <span class="tex-span"><i>n</i></span> distinct elements, it's any non-decreasing subsequence has a maximum of <span class="tex-span"><i>n</i> - 1</span> increasing consequtive element pairs. Using that fact, one could calculate standard longest non-decreasing subsequence dynamic programming on first <span class="tex-span"><i>n</i></span> array blocks (<span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, ..., <i>a</i><sub class="lower-index"><i>n</i><sup class="upper-index">2</sup></sub></span>) and longest non-decreasing subsequence DP on the last <span class="tex-span"><i>n</i></span> array blocks (<span class="tex-span"><i>a</i><sub class="lower-index"><i>nT</i> - <i>n</i> + 1</sub>, ..., <i>a</i><sub class="lower-index"><i>nT</i></sub></span>). All other <span class="tex-span"><i>T</i> - 2<i>n</i></span> blocks between them will make subsegment of consequtive equal elements in longest non-decreasing subsequence.

So, for fixed <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span>, in which longest non-decreasing subsequence of length <span class="tex-span"><i>p</i></span> on first <span class="tex-span"><i>n</i></span> blocks array ends, and for fixed <span class="tex-span"><i>a</i><sub class="lower-index"><i>j</i></sub> ≥ <i>a</i><sub class="lower-index"><i>i</i></sub></span>, in which longest non-decreasing subsequence of length <span class="tex-span"><i>s</i></span> on last <span class="tex-span"><i>n</i></span> blocks array starts, we must update the answer with <span class="tex-span"><i>p</i> + (<i>T</i> - 2<i>n</i>)<i>count</i>(<i>a</i><sub class="lower-index"><i>i</i></sub>) + <i>s</i></span>, where <span class="tex-span"><i>count</i>(<i>x</i>)</span> is the number of occurences of <span class="tex-span"><i>x</i></span> in <span class="tex-span"><i>a</i><sub class="lower-index">1</sub>, ..., <i>a</i><sub class="lower-index"><i>n</i></sub></span> array. This gives us <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/ca2e1829fa31a6050c856b85d6369a8d5172f35d.png" style="max-width: 100.0%;max-height: 100.0%;" /> solution.

**Cdiv1**

Let's fix <span class="tex-span"><i>s</i></span> for every <span class="tex-span">(<i>l</i>, <i>s</i>)</span> pair. One could easily prove, that if subarray contains <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> element, than <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> must be greater-or-equal than <span class="tex-span"><i>a</i><sub class="lower-index"><i>j</i></sub></span> for every <span class="tex-span"><i>j</i></span> such that <span class="tex-span"><i>i</i> ≡ <i>j</i> ± <i>od</i>{<i>gcd</i>(<i>n</i>, <i>s</i>)}</span>. Let's use this idea and fix <span class="tex-span"><i>g</i> = <i>gcd</i>(<i>n</i>, <i>s</i>)</span> (it must be a divisor of <span class="tex-span"><i>n</i></span>). To check if <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> can be in subarray with such constraints, let's for every <span class="tex-span">0 ≤ <i>r</i> &lt; <i>g</i></span> calculate 

<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/e31e7128027ce38b96cb48c434f8acf3b2c64ec8.png" style="max-width: 100.0%;max-height: 100.0%;" />.

It's true that every good subarray must consist of and only of <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2c109515e3f6c2fa3b5760957082a545f7989123.png" style="max-width: 100.0%;max-height: 100.0%;" />. For finding all such subarrays we will use two pointers approach and for every good <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span>, such that <span class="tex-span"><i>a</i><sub class="lower-index">(<i>i</i> - 1) ± <i>od</i>{<i>n</i>}</sub></span> is not good we will find <span class="tex-span"><i>a</i><sub class="lower-index"><i>j</i></sub></span> such that <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub>, <i>a</i><sub class="lower-index">(<i>i</i> + 1) ± <i>od</i>{<i>n</i>}</sub>, ... <i>a</i><sub class="lower-index"><i>j</i></sub></span> are good and <span class="tex-span"><i>a</i><sub class="lower-index">(<i>j</i> + 1) ± <i>od</i>{<i>n</i>})</sub></span> is not good. Let  <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub>, <i>a</i><sub class="lower-index">(<i>i</i> + 1) ± <i>od</i>{<i>n</i>}</sub>, ... <i>a</i><sub class="lower-index"><i>j</i></sub></span> has <span class="tex-span"><i>k</i></span> elements <p>Unable to parse markup [type=CF_TEX]</p> with count <span class="tex-span"><i>k</i>, <i>k</i> - 1, ..., 1</span>. As soon as sum of all <span class="tex-span"><i>k</i></span> is not greater than <span class="tex-span"><i>n</i></span>, we could just increase counts straightforward. There's a case when all <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> are good, in which we must do another increases. Next we must add to the answer only counts of length <span class="tex-span"><i>x</i></span>, such that <span class="tex-span"><i>gcd</i>(<i>x</i>, <i>n</i>) = <i>g</i></span>.

Solution described above has complexity <span class="tex-span"><i>O</i>(<i>d</i>(<i>n</i>)<i>n</i>)</span>, where <span class="tex-span"><i>d</i>(<i>n</i>)</span> is the number of divisors of <span class="tex-span"><i>n</i></span>.

**Ddiv1**

It is a common fact that for a prime <span class="tex-span"><i>p</i></span> and integer <span class="tex-span"><i>n</i></span> maximum <span class="tex-span">α</span>, such that <span class="tex-span"><i>p</i><sup class="upper-index">α</sup>|<i>n</i>!</span> is calculated as <span class="tex-span">α = ≤<i>ft</i></span>