#include <iostream> using namespace std; #define N 1000000 int A[N]; int I[N]; int L[N]; int R[N]; int n; unsigned long long count() { unsigned long long out = 0; for (int i = 0; i < n; i++) { I[A[i]] = i; } L[n - 1] = R[n - 1] = I[n - 1]; for (int i = n - 2; i >= 0; i--) { L[i] = min(I[i], L[i + 1]); R[i] = max(I[i], R[i + 1]); } for (int k = 1, i = n - 1; k <= n; k++, i--) { int f = k / 2 + 1; int l = L[n - f]; int r = R[n - f]; int x = k - (r - l + 1); if (x >= 0) { out += max(0, min(r + x, n - 1) - max(l - x, 0) - k + 2); } } return out; } int main() { ios_base::sync_with_stdio(0); cin >> n; for (int i = 0; i < n; i++) { cin >> A[i]; A[i] -= 1; } cout << 2 * n + 1 << " " << count() << endl; 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 | #include <iostream> using namespace std; #define N 1000000 int A[N]; int I[N]; int L[N]; int R[N]; int n; unsigned long long count() { unsigned long long out = 0; for (int i = 0; i < n; i++) { I[A[i]] = i; } L[n - 1] = R[n - 1] = I[n - 1]; for (int i = n - 2; i >= 0; i--) { L[i] = min(I[i], L[i + 1]); R[i] = max(I[i], R[i + 1]); } for (int k = 1, i = n - 1; k <= n; k++, i--) { int f = k / 2 + 1; int l = L[n - f]; int r = R[n - f]; int x = k - (r - l + 1); if (x >= 0) { out += max(0, min(r + x, n - 1) - max(l - x, 0) - k + 2); } } return out; } int main() { ios_base::sync_with_stdio(0); cin >> n; for (int i = 0; i < n; i++) { cin >> A[i]; A[i] -= 1; } cout << 2 * n + 1 << " " << count() << endl; return 0; } |