fork download
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll n,a[300005],l[300005],r[300005],kq = 0;
  5. int main()
  6. {
  7. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  8. freopen("DIFERENCIJA.inp", "r", stdin);
  9. freopen("DIFERENCIJA.out", "w", stdout);
  10. cin >> n;
  11. memset(l,0,sizeof(l));
  12. memset(r,0,sizeof(r));
  13. for(int i = 1; i <= n; i++)
  14. {
  15. cin >> a[i];
  16. }
  17. for(int i = 1; i <= n; i++)
  18. {
  19. l[i] = i - 1;
  20. while(l[i] > 0 && a[l[i]] >= a[i]) l[i] = l[l[i]];
  21. }
  22. for(int i = n; i >= 1; i--)
  23. {
  24. r[i] = i + 1;
  25. while(r[i] <= n && a[r[i]] > a[i]) r[i] = r[r[i]];
  26. }
  27. for(int i = 1; i <= n; i++)
  28. kq -= a[i]*(i - l[i])*(r[i] - i);
  29. for(int i = 1; i <= n; i++)
  30. {
  31. l[i] = i - 1;
  32. while(l[i] > 0 && a[l[i]] <= a[i]) l[i] = l[l[i]];
  33. }
  34. for(int i = n; i >= 1; i--)
  35. {
  36. r[i] = i + 1;
  37. while(r[i] <= n && a[r[i]] < a[i]) r[i] = r[r[i]];
  38. }
  39. for(int i = 1; i <= n; i++)
  40. kq += a[i]*(i - l[i] )*(r[i] - i);
  41. cout << kq;
  42. }
  43.  
Success #stdin #stdout 0.01s 8528KB
stdin
Standard input is empty
stdout
Standard output is empty