class ST2 {
        long[] a;
        long[] s;
        int n;

        ST2(int n) {
            this.n = n;
            a = new long[n * 4];
            s = new long[n * 4];
        }

        long get(int v, int l, int r, int needL, int needR) {
            if (needR < needL)
                return 0;
            if (l == needL && r == needR)
                return s[v];
            int m = (l + r) >> 1;
            return a[v] * 1L * (needR - needL + 1)
                    + get(v * 2 + 1, l, m, needL, Math.min(needR, m))
                    + get(v * 2 + 2, m + 1, r, Math.max(m + 1, needL), needR);
        }

        void add(int v, int l, int r, int needL, int needR, int val) {
            if (needR < needL)
                return;
            if (l == needL && r == needR) {
                a[v] += val;
                s[v] += (r - l + 1) * 1L * val;
                return;
            }
            int m = (l + r) >> 1;
            add(v * 2 + 1, l, m, needL, Math.min(needR, m), val);
            add(v * 2 + 2, m + 1, r, Math.max(needL, m + 1), needR, val);
            s[v] = s[v * 2 + 1] + s[v * 2 + 2] + a[v] * (r - l + 1);
        }
    }