#include #define rep(i, a, n) for(int i = a; i < n; i++) #define repb(i, a, b) for(int i = a; i >= b; i--) #define all(a) a.begin(), a.end() #define o(a) cout << a << endl #define int long long #define fi first #define se second using namespace std; typedef pair P; const int INF = 1e9; struct Segtree{ int n; vector

dat; Segtree(){} Segtree(int _n){ n = 1; while(n < _n) n *= 2; dat.clear(); rep(i, 0, 2 * n){ dat. push_back(P(-1, i)); } } void update(int k, int a){ dat[k + n - 1].fi = a; dat[k + n - 1].se = k; k += n - 1; while(k > 0){ k = (k - 1) / 2; int l = 2 * k + 1, r = 2 * k + 2; int MAX = -1, id = -1; if(dat[l].fi < dat[r].fi){ MAX = dat[r].fi; id = dat[r].se; }else{ MAX = dat[l].fi; id = dat[l].se; } dat[k].fi = MAX; dat[k].se = id; } } // min[a, b) P query(int a, int b){ return query(a, b, 0, 0, n); } P query(int a, int b, int k, int l, int r){ if(r <= a || b <= l) return P(0, -1); if(a <= l && r <= b) return dat[k]; else{ int mid = (l + r) / 2; P vl = query(a, b, 2 * k + 1, l, mid); P vr = query(a, b, 2 * k + 2, mid, r); return (vl.fi < vr.fi ? vr : vl); // return max(query(a, b, 2 * k + 1, l, mid), query(a, b, 2 * k + 2, mid, r)); } } }; signed main(){ int n, d, k; cin >> n >> d >> k; Segtree sg(n); vector x(n); rep(i, 0, n){ cin >> x[i]; sg.update(i, x[i]); } int ans = -1, idl, idr; rep(i, 0, n){ P p = sg.query(i + 1, min(n - 1, i + k)); int tmp = p.fi - x[i]; // cout << i << " " << p.fi <<" " << p.se << endl; if(tmp > ans){ ans = tmp; idl = i; idr = p.se; } } if(ans <= 0) cout << 0 << endl; else{ cout << ans * k << endl; cout << idl << " " << idr << endl; } }