[Solution] MEX and Array solution codeforces

MEX and Array solution codeforces – Let there be an array 𝑏1,𝑏2,,𝑏𝑘b1,b2,…,bk. Let there be a partition of this array into segments [𝑙1;𝑟1],[𝑙2;𝑟2],,[𝑙𝑐;𝑟𝑐][l1;r1],[l2;r2],…,[lc;rc], where 𝑙1=1l1=1𝑟𝑐=𝑘rc=k, and for any 2𝑖𝑐2≤i≤c holds that 𝑟𝑖1+1=𝑙𝑖ri−1+1=li. In other words, each element of the array belongs to exactly one segment.

Let’s define the cost of a partition as

𝑐+𝑖=1𝑐mex({𝑏𝑙𝑖,𝑏𝑙𝑖+1,,𝑏𝑟𝑖}),c+∑i=1cmex⁡({bli,bli+1,…,bri}),

where mexmex of a set of numbers 𝑆S is the smallest non-negative integer that does not occur in the set 𝑆S. In other words, the cost of a partition is the number of segments plus the sum of MEX over all segments. Let’s define the value of an array 𝑏1,𝑏2,,𝑏𝑘b1,b2,…,bk as the maximum possible cost over all partitions of this array.

MEX and Array solution codeforces

You are given an array 𝑎a of size 𝑛n. Find the sum of values of all its subsegments.

An array 𝑥x is a subsegment of an array 𝑦y if 𝑥x can be obtained from 𝑦y by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The input contains several test cases. The first line contains one integer 𝑡t (1𝑡301≤t≤30) — the number of test cases.

The first line for each test case contains one integer 𝑛n (1𝑛1001≤n≤100) — the length of the array.

The second line contains a sequence of integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖1090≤ai≤109) — the array elements.

It is guaranteed that the sum of the values 𝑛n over all test cases does not exceed 100100.

Output

For each test case print a single integer — the answer to the problem.

MEX and Array solution codeforces

4
2
1 2
3
2 0 1
4
2 0 5 1
5
0 1 1 0 1
output

Copy
4
14
26
48

MEX and Array solution codeforces

In the second test case:

  • The best partition for the subsegment [2,0,1][2,0,1][2],[0,1][2],[0,1]. The cost of this partition equals to 2+mex({2})+mex({0,1})=2+0+2=42+mex⁡({2})+mex⁡({0,1})=2+0+2=4.
  • The best partition for the subsegment [2,0][2,0][2],[0][2],[0]. The cost of this partition equals to 2+mex({2})+mex({0})=2+0+1=32+mex⁡({2})+mex⁡({0})=2+0+1=3
  • The best partition for the subsegment [2][2][2][2]. The cost of this partition equals to 1+mex({2})=1+0=11+mex⁡({2})=1+0=1.
  • The best partition for the subsegment [0,1][0,1][0,1][0,1]. The cost of this partition equals to 1+mex({0,1})=1+2=31+mex⁡({0,1})=1+2=3.
  • The best partition for the subsegment [0][0][0][0]. The cost of this partition equals to 1+mex({0})=1+1+21+mex⁡({0})=1+1+2.
  • The best partition for the subsegment [1][1][1][1]. The cost of this partition equals to 1+mex({1})=1+0=11+mex⁡({1})=1+0=1.

The sum of values over all subsegments equals to 4+3+1+3+2+1=144+3+1+3+2+1=14.

 

Leave a Comment