Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- using namespace std;
- typedef long long ll;
- const ll MOD = 1e9 + 7;
- int main() {
- ios_base::sync_with_stdio(false);
- ll n;
- cin >> n;
- vector<int> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- vector<int> left(n, -1), right(n, n);
- for(int i = 0; i < n; i++) {
- for(int j = i - 1; j >= 0; j--) {
- if(v[j] <= v[i]) {
- left[i] = j;
- break;
- }
- }
- for(int j = i + 1; j < n; j++) {
- if(v[j] <= v[i]) {
- right[i] = j;
- break;
- }
- }
- }
- ll total_subarrays = n * (n + 1) / 2;
- total_subarrays %= MOD;
- ll bad_subarrays = 0;
- for(int i = 0; i < n; i++) {
- ll L = i - left[i], R = right[i] - i;
- bad_subarrays += (L * R) % MOD;
- bad_subarrays %= MOD;
- }
- cout << (total_subarrays - bad_subarrays + MOD) % MOD << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment