1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n;
int a[N], p[N];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int mn[N << 2], mx[N << 2];
void up(int rt) {
mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
void cgmn(int q, int x, int l, int r, int rt) {
if (l == r) {
mn[rt] = x;
return;
}
if (q <= mid)cgmn(q, x, lson);
else cgmn(q, x, rson);
up(rt);
}
void cgmx(int q, int x, int l, int r, int rt) {
if (l == r) {
mx[rt] = x;
return;
}
if (q <= mid)cgmx(q, x, lson);
else cgmx(q, x, rson);
up(rt);
}
int qrymn(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r)return mn[rt];
int ans = INF;
if (ql <= mid)ans = min(ans, qrymn(ql, qr, lson));
if (qr > mid)ans = min(ans, qrymn(ql, qr, rson));
return ans;
}
int qrymx(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r)return mx[rt];
int ans = 0;
if (ql <= mid)ans = max(ans, qrymx(ql, qr, lson));
if (qr > mid)ans = max(ans, qrymx(ql, qr, rson));
return ans;
}
int l[N][2], r[N][2];
ll ans;
int sum[N];
int lowbit(int x) { return x & -x; }
void add(int p, int x) {
for (int i = p; i <= n + 1; i += lowbit(i)) {
sum[i] += x;
}
}
int qry(int r) {
int res = 0;
for (int i = r; i > 0; i -= lowbit(i)) {
res += sum[i];
}
return res;
}
vector<int>vc[N][2];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]), p[a[i]] = i;
fill(mn, mn + 4 * n, n + 1);
for (int i = 1; i <= n; i++) {
l[i][0] = qrymx(a[i], n, 1, n, 1);
int t = l[i][0];
if (t == 0) {
l[i][1] = 0;
cgmx(a[i], i, 1, n, 1);
continue;
}
vc[t][0].push_back(i);
cgmx(a[t], 0, 1, n, 1);
l[i][1] = qrymx(a[i], n, 1, n, 1);
vc[l[i][1]][1].push_back(i);
cgmx(a[t], t, 1, n, 1);
cgmx(a[i], i, 1, n, 1);
}
for (int i = n; i >= 1; i--) {
r[i][0] = qrymn(1, a[i], 1, n, 1);
int t = r[i][0];
if (t == n + 1) {
r[i][1] = t;
cgmn(a[i], i, 1, n, 1);
continue;
}
cgmn(a[t], n + 1, 1, n, 1);
r[i][1] = qrymn(1, a[i], 1, n, 1);
cgmn(a[t], t, 1, n, 1);
cgmn(a[i], i, 1, n, 1);
}
for (int i = 1; i <= n; i++) {
if (l[i][1] == 0 && l[i][0] != 0)
add(i, 1);
}
for (int i = 1; i <= n; i++) {
ans += qry(r[i][1] - 1) - qry(r[i][0] - 1);
for (int u : vc[i][1])add(u, 1);
for (int u : vc[i][0])add(u, -1);
}
printf("%lld\n", ans);
return 0;
}
|
