sone1

// http://darkbzoj.tk/problem/3153

#include <cstdio>

#include <algorithm>

using namespace std;

const int INF = 1 << 29;
const bool rake = false, compress = true;

struct Value {
  int sz, sum, max;

  Value(int sz = 0, int sum = 0, int max = -INF) : sz(sz), sum(sum), max(max) {}
};

struct Tag {
  int k, b;

  Tag(int k = 1, int b = 0) : k(k), b(b) {}

  int operator()(int x) const { return k * x + b; }

  operator bool() const { return k != 1 || b != 0; }
};

Value merge(const Value& lhs, const Value& rhs) {
  return Value(lhs.sum + rhs.sum, max(lhs.max, rhs.max));
}

Value effort(const Tag& op, const Value& v) {
  return Value(v.sz, v.sum * op.k + v.sz * op.b, op(v.max));
}

Tag composite(const Tag& lhs, const Tag& rhs) {
  return Tag(lhs.k * rhs.k, lhs(rhs.b));
}

struct Node {
  union {
    struct { Node *ls, *rs, *vs; };
    Node* ch[3];
  };

  Node* prt;
  Value v, value[2];
  Tag tag[2];

  int relation() const { return find(prt->ch, prt->ch + 3, const_cast<Node*>(this)) - prt->ch; }

  template <bool t> void update();
  template <bool t> void pushDown();
  template <bool t> void change(const Tag& tag);
};

template <bool t> Value get(const Node* o) {
  return o ? effort(o->tag[t], o->value[t]) : Value();
}

template <> void Node::update<rake>() {
  value[rake] = merge(merge(get<rake>(ls), v), merge(get<rake>(rs), get<rake>(vs)));
}

template <> void Node::update<compress>() {
  value[compress] = merge(merge(get<compress>(ls), v), get<compress>(rs));
}

template<> void Node::pushDown<rake>() {
  if (tag[rake]) {

    tag[rake] = Tag();
  }
}

const int N = 100010;


int main() {
  return 0;
}