#include <bits/stdc++.h>
#define N 10005
#define mod 1000007
using namespace std;
long long dp[N];
int arr[N];
int maxi[N];
void solve(){
int n;
cin >> n;
for(int i= 0;i<N;i++)dp[i] = 1;
long long ans = 1;
for(int i=1;i<=n;i++){
cin >> arr[i];
maxi[i+1] = max(maxi[i],arr[i]);
}
for(int i = 0;i<n;i++){
ans = (ans + dp[maxi[n-i]] * (arr[n-i]-1))%mod;
for(int j=1;j<n;j++){
dp[j] = (dp[j] * j + dp[j+1] * (j != n-1)) %mod;
}
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
492 KB |
Output is correct |
2 |
Correct |
4 ms |
492 KB |
Output is correct |
3 |
Correct |
4 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
256 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
492 KB |
Output is correct |
2 |
Correct |
65 ms |
620 KB |
Output is correct |
3 |
Correct |
67 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
255 ms |
568 KB |
Output is correct |
2 |
Correct |
251 ms |
620 KB |
Output is correct |
3 |
Correct |
255 ms |
600 KB |
Output is correct |