[Solution] Minimize the Thickness solution codeforces

Table of Contents

Minimize the Thickness solution codeforces

Minimize the Thickness solution codeforces – You are given a sequence 𝑎=[𝑎1,𝑎2,,𝑎𝑛]a=[a1,a2,…,an] consisting of 𝑛n positive integers.

Let’s call a group of consecutive elements a segment. Each segment is characterized by two indices: the index of its left end and the index of its right end. Denote by 𝑎[𝑙,𝑟]a[l,r] a segment of the sequence 𝑎a with the left end in 𝑙l and the right end in 𝑟r, i.e. 𝑎[𝑙,𝑟]=[𝑎𝑙,𝑎𝑙+1,,𝑎𝑟]a[l,r]=[al,al+1,…,ar].

For example, if 𝑎=[31,4,15,92,6,5]a=[31,4,15,92,6,5], then 𝑎[2,5]=[4,15,92,6]a[2,5]=[4,15,92,6]𝑎[5,5]=[6]a[5,5]=[6]𝑎[1,6]=[31,4,15,92,6,5]a[1,6]=[31,4,15,92,6,5] are segments.

We split the given sequence 𝑎a into segments so that:

  • each element is in exactly one segment;
  • the sums of elements for all segments are equal.

[Solution] Minimize the Thickness solution codeforces

For example, if 𝑎a = [55,45,30,30,40,10055,45,30,30,40,100], then such a sequence can be split into three segments𝑎[1,2]=[55,45]a[1,2]=[55,45]𝑎[3,5]=[30,30,40]a[3,5]=[30,30,40]𝑎[6,6]=[100]a[6,6]=[100]. Each element belongs to exactly segment, the sum of the elements of each segment is 100100.

Let’s define thickness of split as the length of the longest segment. For example, the thickness of the split from the example above is 33.

Find the minimum thickness among all possible splits of the given sequence of 𝑎a into segments in the required way.

Input

The first line contains a single integer 𝑡t (1𝑡1001≤t≤100) — the number of test cases.

Each test case is described by two lines.

The first line of each test case contains a single integer 𝑛n (1𝑛20001≤n≤2000) — the length of the sequence 𝑎a.

The second line of each test case contains exactly 𝑛n integers: 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1061≤ai≤106) — elements of the sequence 𝑎a.

It is guaranteed that the sum of 𝑛n for all test cases does not exceed 20002000.

[Solution] Minimize the Thickness solution codeforces

For each test case, output one integer — the minimum possible thickness of a split of the sequence 𝑎a into segments.

Note that there always exist a split, you can always consider whole sequence as one segment.

Example

input

Copy
4
6
55 45 30 30 40 100
4
10 23 7 13
5
10 55 35 30 65
6
4 1 1 1 1 4

output

Copy
3
4
2
3

[Solution] Minimize the Thickness solution codeforces

The split in the first test case is explained in the statement, it can be shown that it is optimal.

In the second test case, it is possible to split into segments only by leaving a single segment. Then the thickness of this split is equal to the length of the entire sequence, that is, 44.

In the third test case, the optimal split will be [10,55],[35,30],[65][10,55],[35,30],[65]. The thickness of the split equals to 22.

In the fourth test case possible splits are:

  • [4]+[1,1,1,1]+[4][4]+[1,1,1,1]+[4];
  • [4,1,1]+[1,1,4][4,1,1]+[1,1,4].

Leave a Comment