2014-01-24 11:50:59Morris
[ZJ][單調堆] a813 2013高雄市能力競賽高中組 4. 城市觀測
[ZJ][單調堆] a813 2013高雄市能力競賽高中組 4. 城市觀測
/**********************************************************************************/
/* Problem: a813 "2013高雄市能力競賽高中組 4. 城市觀測" from 2013高雄市資訊學科能力複賽*/
/* Language: CPP (693 Bytes) */
/* Result: AC(0.2s, 5.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-01-22 09:02:58 */
/**********************************************************************************/
#include <stdio.h>
#include <stack>
using namespace std;
int n, x[1048576];
int i, j, k;
int main() {
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%d", &x[i]);
stack<int> stk, stk2;
long long ret = 0;
for(i = 0; i < n; i++) {
long long ck = 0;
//if(i) ck = (1 && stk.size() >= 1);
while(!stk.empty() && stk.top() < x[i])
ck += stk2.top(), stk.pop(), stk2.pop();
//ck += stk.size();
if(!stk.empty() && stk.top() == x[i])
ck += stk2.top(), stk2.top()++;
else
stk.push(x[i]), stk2.push(1);
if(stk.size() > 1) ck++;
//printf("ck %lld\n", ck);
ret += ck;
}
printf("%lld\n", ret * 2);
}
return 0;
}