同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22047_Array

2022-5-16 18:21| 发布者: Hocassian| 查看: 22| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-8950667317800-Problem List-采集的数据-后羿采集器.html

Pro.ID

22047

Title

Array

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22047

AC

Submit

Ratio

44.44%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

Array is frequently used when we are programming. We are familiar with it. Here is a problem about array. Do enjoy it and try your best to solve it.

Assume there is an array: a[1], a[2], …, a[n] ( a[i] is positive integer, 1 ≤ i ≤ n )

and a[i] ≤ a[j] ( 1 ≤ i < j ≤ n )

Now we define another array: b[1], b[2], …, b[[a[n]]

b[i] = min{ v | a[v] ≥ i } , 1 ≤ i ≤ a[n]

Finally, the problem is : given the value (n+a[n]), you have to find the maximum of (a[1] + a[2] + … + a[n] + b[1] + b[2] + … + b[a[n]] ).

输入

The first line of the input is a positive integer T. T is the number of the test cases followed. Each test case contains an integer V ( 1 < V < 10000 ) which tell you the value (n+a[n]). There may be one ro several spaces before or after the integer.

输出

Description

Array is frequently used when we are programming. We are familiar with it. Here is a problem about array. Do enjoy it and try your best to solve it.

Assume there is an array: a[1], a[2], …, a[n] ( a[i] is positive integer, 1 ≤ i ≤ n )

and a[i] ≤ a[j] ( 1 ≤ i < j ≤ n )

Now we define another array: b[1], b[2], …, b[[a[n]]

b[i] = min{ v | a[v] ≥ i } , 1 ≤ i ≤ a[n]

Finally, the problem is : given the value (n+a[n]), you have to find the maximum of (a[1] + a[2] + … + a[n] + b[1] + b[2] + … + b[a[n]] ).

Input

Output

The output of the program should consist of one line of output for each test case.

The output of each test case only contains one integer M, M is the maximum of (a[1] + a[2] + … + a[n] + b[1] + b[2] + … + b[a[n]]). No any redundant spaces is needed.