Scribd
Upload
30 views2 pages

Max Arrays from Sorted Input

The document describes a programming problem from Codeforces Round 1027 (Div. 3) titled 'Need More Arrays'. Participants are tasked with determining the maximum number of new arrays that can be created from a given sorted array by selectively removing elements. The input consists of multiple test cases, each specifying the length of the array and its elements, with constraints on the number of test cases and the total number of elements across all cases.

Uploaded by

potosad380
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
30 views2 pages

Max Arrays from Sorted Input

The document describes a programming problem from Codeforces Round 1027 (Div. 3) titled 'Need More Arrays'. Participants are tasked with determining the maximum number of new arrays that can be created from a given sorted array by selectively removing elements. The input consists of multiple test cases, each specifying the length of the array and its elements, with constraints on the number of test cases and the total number of elements across all cases.

Uploaded by

potosad380
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

 |

Durjoy1971 | Logout

HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP

PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS STANDINGS CUSTOM INVOCATION

Codeforces Round 1027 (Div. 3)


C. Need More Arrays System testing
time limit per test: 2 seconds
67%
memory limit per test: 256 megabytes

Given an array a and n integers. It is sorted in non-decreasing order, that is, ai ≤ ai+1 for all
1 ≤ i < n.

→ Contest materials
You can remove any number of elements from the array (including the option of not removing any
at all) without changing the order of the remaining elements. After the removals, the following will Announcement
occur:

a1 is written to a new array;


if a1 + 1 < a2 , then a2 is written to a new array; otherwise, a2 is written to the same array
as a1 ;
if a2 + 1 < a3 , then a3 is written to a new array; otherwise, a3 is written to the same array
as a2 ;
⋯

For example, if a = [1, 2, 4, 6] , then:

a1 = 1 is written to the new array, resulting in arrays: [1] ;


a1 + 1 = 2 , so a2 = 2 is added to the existing array, resulting in arrays: [1, 2];
a2 + 1 = 3 , so a3 = 4 is written to a new array, resulting in arrays: [1, 2] and [4] ;

a3 + 1 = 5 , so a4 = 6 is written to a new array, resulting in arrays: [1, 2], [4] , and [6] .

Your task is to remove elements in such a way that the described algorithm creates as many
arrays as possible. If you remove all elements from the array, no new arrays will be created.

Input
The first line of input contains one integer t (1
4
≤ t ≤ 10 ) — the number of test cases.

The first line of each test case contains one integer n (1


5
≤ n ≤ 2 ⋅ 10 ) — the length of the
array.

6
The second line of each test case contains n integers a1 , a2 , … , an (1 ≤ ai ≤ 10 ,
ai ≤ ai+1 ) — the elements of the array.

5
It is guaranteed that the sum of n across all test cases does not exceed 2 ⋅ 10 .

Output
For each test case, output one integer — the maximum number of arrays that can be obtained by
removing any (possibly zero) number of elements.

Example
input Copy

6
6
1 2 3 4 5 6
3
1 2 3
4
1 2 2 4
1
2
3
1 4 8
2
1 1
output Copy

3
2
2
1
3
1
Note
In the first example, you can remove a3 and a5 , then a = [1, 2, 4, 6] , the process of forming
arrays for it is shown in the statement.

In the second example, you need to remove a2 , after which a = [1, 3] , and the arrays [1] and
[3] will be written.

In the third example, no removals are needed; for a = [1, 2, 2, 4] , the arrays [1, 2, 2] and [4] will
be written.

Codeforces (c) Copyright 2010-2025 Mike Mirzayanov


The only programming contests Web 2.0 platform
Server time: May/27/2025 12:20:43UTC+6 (l3).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions

Supported by

You might also like