Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 128  

Solved: 25

Description

晴天有非常严重的选择恐惧症，每次吃饭前他都在纠结到底吃什么。。今天又到了吃饭的时候了。

重光：我给你一个包含n个不同整数的序列a，如果它所有连续子序列的价值和是素数咱们就吃米，不然就吃面。

定义一个序列的价值为序列中所有元素的最小值。

晴天：这不是分分钟给你算出来。

嗯...十分钟过去了，晴天选择死亡。

这个任务就交给你啦。

算出所有连续子序列的价值和。

Input

第一行输入一个整数t，代表有t组测试数据。

每组数据第一行包含一个整数n，表示序列a的元素个数。

接下来一行包含n个整数，表示序列a。

0<=n<=50000，1<=ai<=50000。

Output

对于每组数据输出一个整数，表示序列a的所有连续子序列的价值和。

Sample Input

1

3

1 2 3

Sample Output

10

对于一个没有重复元素的序列，每一个元素作为序列的价值是唯一的，所以用一遍for循环扫一遍，让每个元素作为子序列价值，统计就可以了。

对于序列中的任一个元素x，找到左边比他大的元素与他距离的最远值与他的距离a和右边比他大的最远的值与他的距离b。他的贡献就是（a+1）*（b+1）*x;

有一个很好的已知条件就是数字没有重复的，利用这个特点，现将数列进行升序排。对于最小一个，他可以到达的一定是两头。再放下一个，他可以到达的就变成了比他小的到另一头，一直放下去，问题就得到了解决。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define space " "#define LOCALusing namespace std;//typedef __int64 Int;typedef long long Long;const int INF = 0x3f3f3f3f;const int MAXN = 50000 + 10;vector
          
            G;struct node{ int x, id;}data[MAXN];bool cmp(node a, node b) { return a.x < b.x;}int main() { int t, n; scanf("%d", &t); while (t--) { scanf("%d", &n); G.clear(); for (int i = 1; i <= n; i++) { scanf("%d", &data[i].x); data[i].id = i; } Long ans = 0; G.push_back(0), G.push_back(n + 1); sort(data + 1, data + 1 + n, cmp); for (int i = 1; i <= n; i++) { int k = lower_bound(G.begin(), G.end(), data[i].id) - G.begin(); //cout << G[k] << space << G[k - 1] << endl; ans += (G[k] - data[i].id)*(data[i].id - G[k - 1])*data[i].x; G.insert(G.begin() + k, data[i].id); } printf("%lld\n", ans); } return 0;}