/*
问题描述
大兵们站成一行横队。排长发出命令：立正！向右看——齐！！
唰的一声，所有大兵都向右看。
由于大兵们的身高不全相同，向右看的时候就能看到比他矮的士兵的头了。
如果他右边有一个人大于等于他的身高，那么他就看不到那个人右边的人了。
假设总共n个士兵，第i个士兵看到ki个头，问S=k1+k2+k3+..+kn

输入
多组测试数据，第一行是n(1<=n<=1e5)，第二行是n个数，表示k1,k2,....,kn，
kn范围在1到1e9

输出
对于每组数据要输出一行，包含S的值，测试数据保证s<2e9

样例输入
2
1 2
3
1 2 3
3
3 2 1
3
1 1 1
5
1 5 2 9 3

样例输出
1
3
2
2
6

提示
对于：
5
1 5 2 9 3
5看到1；2看到5；9看到1,5,2；3看到9；

难度：easy
*/
#include <stdio.h>

int main()
{
 int n,a[ 100000];
 int MAX,k;
 long count;

 while (scanf("%d",&n)!=EOF)
 {
  MAX=0;
  count=0;
  
  for (k=0;k<n;k++)
  {
   scanf("%d",&a[k ]);

   if (k!=0)
   {
    if (a[ k]>a[ MAX])
    {
     MAX=k;
     count = count+k;
    }
    else
    {
     for(int i=k-1;i>=MAX;i--)
     {

      if (a[i ]<a[k ])
       count++;
      else
      {
       count++;
       break;
      }
     }
    }
   }
  }
  printf("%d\n",count);
 }

 return 0;
}

评论