1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <algorithm>
#include <cstdio>

long long int current_time;

struct TreeNode {
  int slowest_grass_;
  int fastest_grass_;
  long long int lowest_grass_;
  long long int highest_grass_;
  long long int mass_of_grass_;
  long long int sum_of_velocities_;
  long long int last_update_;
  long long int setting_time_;
  long long int setting_height_;

  void InitJoin(const TreeNode& l, const TreeNode& r) {
    slowest_grass_ = std::min(l.slowest_grass_, r.slowest_grass_);
    fastest_grass_ = std::max(l.fastest_grass_, r.fastest_grass_);
    sum_of_velocities_ = l.sum_of_velocities_ + r.sum_of_velocities_;
  }

  void Join(const TreeNode& l, const TreeNode& r) {
    lowest_grass_ = std::min(l.lowest_grass_, r.lowest_grass_);
    highest_grass_ = std::max(l.highest_grass_, r.highest_grass_);
    mass_of_grass_ = l.mass_of_grass_ + r.mass_of_grass_;
    sum_of_velocities_ = l.sum_of_velocities_ + r.sum_of_velocities_;
  }

  void SetTo(long long int height, TreeNode* l, TreeNode* r, int length) {
    setting_time_ = current_time;
    setting_height_ = height;
    Update(l, r, length);
  }

  void Update(TreeNode* l, TreeNode* r, int length) {
    if (setting_time_ >= 0) {
      lowest_grass_ = setting_height_;
      highest_grass_ = setting_height_;
      mass_of_grass_ = length * setting_height_;
      last_update_ = setting_time_;
      if (l != nullptr and r != nullptr) {  // Not a leaf.
        r->setting_time_ = l->setting_time_ = setting_time_;
        r->setting_height_ = l->setting_height_ = setting_height_;
      }
      setting_time_ = -1ll;
    }
    const long long int time_difference = current_time - last_update_;
    lowest_grass_ += time_difference * slowest_grass_;
    highest_grass_ += time_difference * fastest_grass_;
    mass_of_grass_ += time_difference * sum_of_velocities_;
    last_update_ = current_time;
  }
};

int n2;

const int moreThanBase = 524288 + 5;

TreeNode tree[moreThanBase * 2 + 5];

TreeNode* LeftSon(int w) {
  return w < n2 ? &tree[w * 2] : nullptr;
}

TreeNode* RightSon(int w) {
  return w < n2 ? &tree[w * 2 + 1] : nullptr;
}

long long int Cut(int w, int a, int b, long long height) {
  long long result = 0ll;
  TreeNode& t = tree[w];
  t.Update(LeftSon(w), RightSon(w), b - a + 1);
  if (t.lowest_grass_ >= height) {
    result = t.mass_of_grass_ - (b - a + 1) * height;
    t.SetTo(height, LeftSon(w), RightSon(w), b - a + 1);
  } else if (t.highest_grass_ <= height) {
    // Do nothing.
  } else if (a != b) {
    result = Cut(w * 2, a, (a + b) / 2, height)
        + Cut(w * 2 + 1, (a + b + 1) / 2, b, height);
    t.Join(tree[w * 2], tree[w * 2 + 1]);
  }
  return result;
}

int n, m;
int a_i[moreThanBase + 5];

int main() {
  scanf("%d%d", &n, &m);
  n2 = 1;
  while (n2 < n) {
    n2 *= 2;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &a_i[i]);
  }
  std::sort(a_i, a_i + n2);  // Additional zeroes are sorted on purpose.
  for (int i = 0; i < n2; i++) {
    tree[n2 + i].slowest_grass_ = a_i[i];
    tree[n2 + i].fastest_grass_ = a_i[i];
    tree[n2 + i].sum_of_velocities_ = a_i[i];
  }
  for (int i = n2 - 1; i >= 1; i--) {
    tree[i].InitJoin(tree[i * 2], tree[i * 2 + 1]);
  }
  while (m--) {
    long long int height;
    scanf("%lld%lld", &current_time, &height);  // current_time = d, height = b
    printf("%lld\n", Cut(1, 0, n2 - 1, height));
  }
  return 0;
}