[4月月赛]

佚名 7年前 (2019-05-15) 随笔 566人围观抢沙发百度已收录

我好像不会做

Description

plw现在在一个仓库里当搬砖工，这个仓库存放的是n种不同颜色的砖块，颜色编号从1-n。plw突然兴起想堆一个墙，为了美观，plw决定按照1-n的颜色编号顺序从下往上垒成一列。

有一个传送带和仓库相连，传送带按照 a[1] a[2] ... a[n] 的颜色顺序源源不断的送砖进来。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

如果当前送进来的砖恰好是plw所需要的， plw就会把这个砖垒进墙内。否则plw就把这个砖放进一旁的次元栈里面，次元栈可以存放无数个砖。

每次plw新垒上一个砖后，他会看看次元栈的顶部的砖是不是所需要的（如果次元栈中有砖），如果是他就会从次元栈中取出这个砖，并且垒上去。

如果plw没办法得到想要的砖，plw就会开启传送带，传送带会送入下一个砖。

plw想知道他需要至少启动多少次传送带，才能完成目标。

启动一次传送带会送入一块砖。

PS：

假定plw无限高，身高为 INF.

Input

n <= 1e5

a[1] ... a[n] 为1-n的排列。

output

输出一个数，为需要多少个砖块。

Examples

Input

12
8 9 10 6 5 7 11 3 4 1 2 12

Output

正确解法：

开long long

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <cctype>
10 #include <sstream>
11 using namespace std;
12 typedef long long ll;
13 const int inf=0x7fffffff;
14 const int N=100000+100;
15 const int M=50000+10;
16 const int MOD=998244353;
17 const double PI=acos(-1.0);
18 int n;
19 ll a[N];
20 ll l[N],r[N],b[N],bok[N],ans=0,now=0;
21 int main()
22 {
23     scanf("%d",&n);
24     for(int i=1;i<=n;i++)
25     {
26         scanf("%lld",&a[i]);
27         l[i]=i-1;
28         r[i]=i+1;
29         b[a[i]]=i;
30     }
31     for(int i=1;i<=n;i++)
32     {
33         if(bok[i]==0)
34         {
35             now=i;
36             ans++;
37             for(int pos=b[i];pos<=n;pos=b[now])
38             {
39                 l[pos]=pos-1;
40                 r[pos]=pos+1;
41                 bok[now]=1;
42                 now++;
43                 while(a[l[pos]]==now||a[r[pos]]==now)
44                 {
45                     if(a[l[pos]]==now)
46                     {
47                         l[pos]--;
48                         bok[now]=1;
49                         now++;
50                     }
51                     else
52                     {
53                         r[pos]++;
54                         bok[now]=1;
55                         now++;
56                     }
57                 }
58                 if(b[now]<r[pos])   break;
59             }
60 
61         }
62     }
63     cout<<ans*n-n+b[n]<<endl;
64 
65     return 0;
66 }