#define MAX_N 350
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
using namespace std;

int arr[350][350];//原图
int n;
int range;
vector<pair<int, int>> g[203]; //g[i] = {j,x} 记录i--j号桩子之间的最短距离为x
int county = 0;//充电桩数量

void init(int N, int mRange, int mMap[MAX_N][MAX_N])
{
    n = N;
    for (int i = 0; i < county; i++)
    {
        g[i].clear();
    }
    county = 0;
    range = mRange;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            arr[i][j] = mMap[i][j];
        }
    }
}

int dir[4][2] = { {-1,0,},{0,-1},{0,1},{1,0} }; // 偏移数组

void add(int mID, int mRow, int mCol)
{
    county++;
    arr[mRow][mCol] = mID + 2; //用同一张图进行存储 大于1的点表示是桩子
    if (mID <= 0)
    {
        return;
    }
    int dist[350][350] = { 0 };
    queue<pair<int, int>> q;
    q.push({ mRow,mCol });
    while (!q.empty())
    {
        pair<int, int> temp = q.front();
        int x = temp.first;
        int y = temp.second;
        q.pop();
        if (dist[x][y] > range)
        {
            return;
        }
        if (arr[x][y] >= 2 && arr[x][y] - 2 != mID)
        {
            g[mID].push_back({ arr[x][y] - 2,dist[x][y] });
            g[arr[x][y] - 2].push_back({ mID,dist[x][y] }); //每加一个桩子 就维护一下邻接表
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || dist[nx][ny] + 1 >= range || arr[nx][ny] == 1)
            {
                continue;
            }
            if (dist[nx][ny] == 0)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({ nx,ny });
            }
        }
    }
    int d = 0;
}

int distance(int mFrom, int mTo)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //logn版本的dijkstra算法需要用到优先队列 将第一个距离最短的放在队首
    vector<int> dist(county, INT_MAX);
    pq.push({ 0,mFrom });
    dist[mFrom] = 0;
    while (!pq.empty())
    {
        auto temp = pq.top();
        int node = temp.second;
        int currdist = temp.first;
        pq.pop();
        if (node == mTo)
        {
            return currdist;
        }
        for (auto nbr : g[node])
        {
            if (dist[nbr.first] > currdist + nbr.second)
            {
                dist[nbr.first] = currdist + nbr.second;
                pq.push({ dist[nbr.first],nbr.first });
            }
        }
    }
    return -1;
}

#include <bits/stdc++.h>
using namespace std;
#define kl k<<1
#define kr k<<1|1
const int N = 1e5 + 5;

int n;
int h[N], t[N << 2];

void build(int L, int R, int k) {
    if (L < R) {
        int mid = (L + R) >> 1;
        build(L, mid, kl);
        build(mid + 1, R, kr);
    }
    t[k] = L;
}

void update(int L, int R, int x, int k) {
    if (L == R) return;
    int mid = (L + R) >> 1;
    if (x <= mid) update(L, mid, x, kl);
    else update(mid + 1, R, x, kr);
    t[k] = h[t[kl]] >= h[t[kr]] ? t[kl] : t[kr];
}

int query(int L, int R, int l, int r, int k) {
    if (l <= L && r >= R) return t[k];
    int x = 0, y = 0, mid = (L + R) >> 1;
    if (l <= mid) x = query(L, mid, l, r, kl);
    if (r > mid) y = query(mid + 1, R, l, r, kr);
    return h[x] >= h[y] ? x : y;
}

int cla() {
    int s = 0;
    int x, y, z;
    z = query(1, n, 1, n, 1);
    s += h[z];
    x = z;
    while (x > 1 && h[x]) {
        y = query(1, n, 1, x - 1, 1);
        s += h[y] * (x - y);
        x = y;
    }

    x = z;
    while (x < n && h[x]) {
        y = query(1, n, x + 1, n, 1);
        s += h[y] * (y - x);
        x = y;
    }
    return s;
}

void init(int _n) {
    n = _n;
    build(1, n, 1);
    memset(h, 0, sizeof h);
    h[0] = -1;
}

int stock(int x, int v) {
    h[x] += v;
    update(1, n, x, 1);
    return cla();
}

int ship(int x, int v) {
    h[x] -= v;
    update(1, n, x, 1);
    return cla();;
}

int getHeight(int x) {
    return h[x];
}