#include <bits/stdc++.h> using namespace std; long long solve(int n, vector <int> &arr) { vector <int> pos(n); for (int i = 0; i < n; i++) { pos[arr[i]] = i; } int l = n, r = -1; long long ans = 0; for (int x = 1; 2 * x - 2 <= n; x++) { int i = n - x; l = min(l, pos[i]); r = max(r, pos[i]); for (int k : {2 * x - 1, 2 * x - 2}) if (k >= 1 && k <= n) { int remain = k - (r - l + 1); if (remain < 0) { continue; } int tMin = max(0, remain - (n - 1 - r)); int tMax = min(l, remain); ans += max(0, tMax - tMin + 1); } } return ans; } int main() { ios_base::sync_with_stdio(false); int n; cin >> n; vector <int> arr(n); for (int &ai : arr) { cin >> ai; ai--; } cout << 2 * n + 1 << ' ' << solve(n, arr); return 0; }
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 | #include <bits/stdc++.h> using namespace std; long long solve(int n, vector <int> &arr) { vector <int> pos(n); for (int i = 0; i < n; i++) { pos[arr[i]] = i; } int l = n, r = -1; long long ans = 0; for (int x = 1; 2 * x - 2 <= n; x++) { int i = n - x; l = min(l, pos[i]); r = max(r, pos[i]); for (int k : {2 * x - 1, 2 * x - 2}) if (k >= 1 && k <= n) { int remain = k - (r - l + 1); if (remain < 0) { continue; } int tMin = max(0, remain - (n - 1 - r)); int tMax = min(l, remain); ans += max(0, tMax - tMin + 1); } } return ans; } int main() { ios_base::sync_with_stdio(false); int n; cin >> n; vector <int> arr(n); for (int &ai : arr) { cin >> ai; ai--; } cout << 2 * n + 1 << ' ' << solve(n, arr); return 0; } |