#include <iostream> #include <vector> typedef long long ll; using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; vector<int> a(n); vector<int> idx(n + 1); for(int i = 0; i < n; ++i) { cin>>a[i]; idx[a[i]] = i; } ll total = 0; int left = idx[n]; int right = idx[n]; for(int i = 0; i < n - 1; ++i) { int cur_idx = idx[n - i]; left = min(left, cur_idx); right = max(right, cur_idx); int next_idx = idx[n - i - 1]; if(next_idx > left && next_idx < right) continue; // currently examined interval has next element in it - we'll count it in the next iteration int cur_len = right - left + 1; int max_addition = i - (cur_len - (i + 1)); if(max_addition < 0) continue; // too large interval int max_left = max(0, left - max_addition); int min_right = min(n - 1, right + max_addition); if(next_idx < left) max_left = max(max_left, next_idx + 1); if(next_idx > right) min_right = min(min_right, next_idx - 1); int len_a = left - max_left; int len_b = min_right - right; if(len_a < len_b) swap(len_a, len_b); int first = min(max_addition - len_a + 1, len_b + 1); int last = len_b + 1; total += (first + last) * (last - first + 1) / 2 + last * (len_a - (last - first + 1) + 1); } ++total; // the whole input int result = n + (n + 2)/2 + (n + 1)/2; cout<<result<<' '<<total; } /* 5 1 4 3 5 2 ~ 11 5 5 1 2 3 4 5 ~ 11 5 5 4 1 3 2 5 ~ 11 2 5 2 3 4 5 1 ~ 11 7 6 1 2 3 4 5 6 ~ 13 6 6 4 5 6 1 2 3 ~ 13 7 6 4 5 2 1 6 3 ~ 13 3 */
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 | #include <iostream> #include <vector> typedef long long ll; using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; vector<int> a(n); vector<int> idx(n + 1); for(int i = 0; i < n; ++i) { cin>>a[i]; idx[a[i]] = i; } ll total = 0; int left = idx[n]; int right = idx[n]; for(int i = 0; i < n - 1; ++i) { int cur_idx = idx[n - i]; left = min(left, cur_idx); right = max(right, cur_idx); int next_idx = idx[n - i - 1]; if(next_idx > left && next_idx < right) continue; // currently examined interval has next element in it - we'll count it in the next iteration int cur_len = right - left + 1; int max_addition = i - (cur_len - (i + 1)); if(max_addition < 0) continue; // too large interval int max_left = max(0, left - max_addition); int min_right = min(n - 1, right + max_addition); if(next_idx < left) max_left = max(max_left, next_idx + 1); if(next_idx > right) min_right = min(min_right, next_idx - 1); int len_a = left - max_left; int len_b = min_right - right; if(len_a < len_b) swap(len_a, len_b); int first = min(max_addition - len_a + 1, len_b + 1); int last = len_b + 1; total += (first + last) * (last - first + 1) / 2 + last * (len_a - (last - first + 1) + 1); } ++total; // the whole input int result = n + (n + 2)/2 + (n + 1)/2; cout<<result<<' '<<total; } /* 5 1 4 3 5 2 ~ 11 5 5 1 2 3 4 5 ~ 11 5 5 4 1 3 2 5 ~ 11 2 5 2 3 4 5 1 ~ 11 7 6 1 2 3 4 5 6 ~ 13 6 6 4 5 6 1 2 3 ~ 13 7 6 4 5 2 1 6 3 ~ 13 3 */ |