Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MaxN = 1000010;
- const int mod = 1e9 + 7;
- int v[MaxN], left1[MaxN], left2[MaxN], right1[MaxN], right2[MaxN];
- int multiply(int a, int b, int c, int d) {
- return (1LL * ((1LL * a * b) % mod) * ((1LL * c * d) % mod)) % mod;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- //ifstream fin("rectangles.in");
- //ofstream fout("rectangles.out");
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> v[i];
- left1[i] = left2[i] = 0;
- right1[i] = right2[i] = n + 1;
- }
- stack<int> st1, st2, aux;
- for (int i = 1; i <= n; i++) {
- while (!st2.empty() && v[i] > v[st2.top()]) {
- right2[st2.top()] = i;
- st2.pop();
- }
- while (!st1.empty() && v[i] > v[st1.top()]) {
- right1[st1.top()] = i;
- aux.push(st1.top());
- st1.pop();
- }
- st1.push(i);
- for (; !aux.empty(); aux.pop())
- st2.push(aux.top());
- }
- for (; !st1.empty(); st1.pop());
- for (; !st2.empty(); st2.pop());
- for (int i = n; i >= 1; i--) {
- while (!st2.empty() && v[i] >= v[st2.top()]) {
- left2[st2.top()] = i;
- st2.pop();
- }
- while (!st1.empty() && v[i] >= v[st1.top()]) {
- left1[st1.top()] = i;
- aux.push(st1.top());
- st1.pop();
- }
- st1.push(i);
- for (; !aux.empty(); aux.pop())
- st2.push(aux.top());
- }
- long long sol = 0;
- for (int i = 1; i <= n; i++) {
- if (left1[i] > 0) {
- int a = left1[i] - left2[i];
- int b = right1[i] - i;
- sol = (sol + multiply(a, b, v[i], v[left1[i]])) % mod;
- }
- if (right1[i] < n + 1) {
- int a = i - left1[i];
- int b = right2[i] - right1[i];
- sol = (sol + multiply(a, b, v[i], v[right1[i]])) % mod;
- }
- }
- cout << sol << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement