[Solution] Twist I Codeforces Solution VK Cup

C1. Twist I

test time limit

2 seconds

memory limit per test

512 megabytes

input

standard input

conclusion

standard output

In this version of the task𝑛 ≤ 50$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">fifty</span></span>}$and𝑎𝑖≤ 100${\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">i</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">100</span></span>}$.

Vika has already done𝑛$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}$commits in version control.𝑖$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">i</span></span>}$th commit was made in𝑎𝑖${\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">i</span></span>}}$Vicky's day at the company. On some days, Vika might make several commits, and on others, none.

Vika is interested in such segments of consecutive days that she has at least one commit on each of these days. The longer the longest such segment, the more productive employee she will feel.

Vika recently found a way to push the time of any commit forward, but no more than a day. In this way,𝑖$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">i</span></span>}$-th commit can now be "made" either in𝑎𝑖${\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">i</span></span>}}$th, or in(𝑎𝑖+ 1 )$<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">(</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">i</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">+</span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">one</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">)</span></span>$th day. The time of each commit can be tweaked independently of the others - in particular, you can either leave all commits at the original time, or move all commits exactly one day ahead.

Find the length of the longest possible span of consecutive days, each of which the Wiki will show at least one commit in its profile, after possibly twisting the time of some commits.

Input data

Each test consists of several sets of input data. The first line contains one integer𝑡$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">t</span></span>}$(1 ≤ 𝑡 ≤ 100$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">one</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">t</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">100</span></span>}$) is the number of test cases. The following is a description of the input data sets.

The first line of each test case contains one integer𝑛$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}$(1 ≤ 𝑛 ≤ 50$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">one</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">fifty</span></span>}$) is the number of commits.

The second line contains𝑛$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}$integers𝑎one,𝑎2, … ,𝑎𝑛${\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">one</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">2</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\dots </span></span><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}}$in non-decreasing order (1 ≤𝑎one≤𝑎2≤ … ≤𝑎𝑛≤ 100$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">one</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">one</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">2</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\dots </span></span><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">100</span></span>}$) are the numbers of the days on which the commits were made.

Output

For each test case, print a single integer — the maximum possible length of a segment of days, each of which will display at least one commit in Wiki's profile, after possibly twisting the time of some commits forward by no more than a day.