# Cod sursa(job #2750788)

Utilizator Data 13 mai 2021 11:08:40 Secv 100 cpp-64 done Arhiva de probleme 1.69 kb
``````//#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
ifstream cin("secv.in");
ofstream cout("secv.out");
unordered_map <int,int> um;
vector <int> f[5005];
int v[5005],norm[5005],d[5005],nex[5005],gigel[5005];
void solve(int i,int total){
if(d[i]!=-2)
return;
if(v[i]==total){
d[i]=i;
return;
}
if(nex[i]==-1){
d[i]=-1;
return;
}
solve(nex[i],total);
d[i]=d[nex[i]];
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i];
norm[i]=v[i];
}
sort(norm+1,norm+n+1);
int cur=0;
norm[0]=-1;
for(int i=1;i<=n;i++){
if(norm[i]!=norm[i-1]){
cur++;
um[norm[i]]=cur;
}
}
for(int i=1;i<=n;i++){
v[i]=um[v[i]];
}
for(int i=1;i<=n;i++){
f[v[i]].push_back(i);
}
for(int i=1;i<=cur;i++){
gigel[i]=0;
}
for(int i=1;i<=n;i++){
if(v[i]==cur){
nex[i]=i;
gigel[v[i]]++;
continue;
}
if(gigel[v[i]+1]>=f[v[i]+1].size()){
nex[i]=-1;
}
else
nex[i]=f[v[i]+1][gigel[v[i]+1]];
gigel[v[i]]++;
}
for(int i=1;i<=n;i++){
d[i]=-2;
//cout<<nex[i]<<" ";
}
//cout<<"\n";
for(int i=1;i<=n;i++){
solve(i,cur);
//cout<<d[i]<<" ";
}
int sol=999999;
for(int i=1;i<=n;i++){
if(v[i]==1 and d[i]!=-1){
sol=min(sol,d[i]-i+1);
}
}
if(sol==999999)
sol=-1;
cout<<sol;
return 0;
}
``````