2020-2021 ACM-ICPC, Asia Seoul Regional Contest
===
比賽鏈結
---
https://codeforces.com/gym/102920/

比賽影片
---
No

記分板

---

題解
---
### A. Autonomous Vehicle
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### B. Commemorative Dice
---
#### 題目摘要

#### 想法
隊友秒ㄌ

:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    vector<int> a(6), b(6);
    rep (i, 0, 6) cin >> a[i];
    rep (i, 0, 6) cin >> b[i];
    int ans = 0;
    rep (i, 0, 6) rep (j, 0, 6) {
        if (a[i] > b[j]) ans++;
    }
    int g = __gcd(ans, 36);
    cout << ans / g << '/' << 36 / g << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

:::

### C. Dessert Café
---
#### 題目摘要
給定幾個公寓的預定地，所有點都可以是一個預選地，然後定義一個好的預選地p為對於其他所有預選地q，他都可以找到一個公寓預定地k使得dis(p,k) < dis(q,k)，要你輸出所有好的點

#### 想法
可以觀察到，如果一個點有兩個子樹都有公寓預定地，那麼這個點對於B子樹的預定地的距離，一定比A子樹的所有點短，反之亦然，因此只要關注每個點是否有兩個以上的子樹有公寓預定地即可，記得加上公寓預定地本身

:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }

const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }

ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    int n, k; cin >> n >> k;
    vector<vector<pii>> adj(n);
    rep (i, 0, n - 1) {
        int a, b, c; cin >> a >> b >> c;
        a--, b--;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    } 
    vector<int> col(n, 0);
    rep (i, 0, k) {
        int a; cin >> a;
        a--;
        col[a] = 1;
    }
    vector<int> sz(n, 0), dep(n);
    int ans = 0;
    auto dfs = [&](auto self, int u, int pa) -> void {
        sz[u] = col[u];
        int cnt = 0;
        for (auto [v, w] : adj[u]) {
            if (v == pa) continue;
            dep[v] = dep[u] + 1;
            self(self, v, u);
            sz[u] += sz[v];
            cnt += sz[v] > 0;
        }
        if (k - sz[u] > 0) cnt++;
        if (col[u] == 1) ans++;
        else {
            if (cnt >= 2) ans++;
        }
    };
    dep[0] = 0;
    dfs(dfs, 0, -1);
    cout << ans << '\n';
}

int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

:::

### D. Electric Vehicle
---
#### 題目摘要
#### 想法

:::spoiler 實作

:::

### E. Imprecise Computer
---
#### 題目摘要
有$n$個人雙雙比賽，編號$1到n$。編號$i$和編號$j$比賽$(i>j)$為，若$i-j<2$，則$j$有可能打贏$i$，否則一定$i$打贏$j$。總共會有兩輪比賽，定義$r_i(k)$為第$i$場第$k$個人打贏多少人，題目會給你一個序列$d$，$d(i)=|r_1(i)-r_2(i)|,\ \ 1\le i\le n$的值，問有沒有一組比賽滿足它
#### 想法
在同一場比賽中，將第$i和i+1$的人同時考慮，若$i打贏i+1$，則$r(i)$會+1，$r(i+1)$會-1，否則$r(i)=i,\ r(i+1)=i+1$。而當考慮到兩場比賽的組合，相當於$d(i)與d(i+1)$的改變量有$(1, -1),(0, 0),(-1, 1)$三種可能
因此題目轉換成對一個初始為0的序列做操作，操作能對$i與i+1$的位置增加$(1, -1),(0, 0),(-1, 1)$，問能不能元素取絕對值是$d$。記一個$dp_{i, j}$為從$1到i-1$的位置元素的絕對值已經滿足$d$了，且第$i$個元素是$j$，好好轉移就好了
:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ORENOOSHIKYOUMOKAWAIII ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
 
template<class T> bool chmin(T &a, T b){return (a>b)?a=b, true:false;}
template<class T> bool chmax(T &a, T b){return (a<b)?a=b, true:false;}
template<class T> T fpow(T x, ll k){T res=1;while(k){if (k&1) res=res*x;x=x*x, k>>=1;}return res;}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rand(int l, int r){return uniform_int_distribution<int>(l, r)(rng);}
 
const double eps=1e-9;
const int IINF=1e9+7;
const ll LINF=1e18+5;
const int MOD1=998244353, MOD2=1e9+7;
 
template <class T> istream& operator>> (istream& cin, pair<T, T>& tmp){cin >> tmp.F >> tmp.S;return cin;} 
template <class T> istream& operator>> (istream& cin, vector<T>& tmp){for(auto &v:tmp) cin >> v;return cin;}
template <class T> ostream& operator<< (ostream& cout, pair<T, T>& tmp){cout << tmp.F << ' ' << tmp.S;return cout;} 
template <class T> ostream& operator<< (ostream& cout, vector<T>& tmp){for(auto v:tmp) cout << v << ' ';return cout;}
 
const int N=1e6+10;
bool dp[N][5];
 
void _solve(){
    int n;
    cin >> n;
    vector<int> v(n);
    cin >> v;
    if (v[0]==0) dp[1][2]=1;
    else if (v[0]==1) dp[1][1]=dp[1][3]=1;
    for(int i=2;i<n;i++){
        for(int j=-2;j<=2;j++) if (dp[i-1][j+2]) {
            if (abs(j+1)==v[i-1]) dp[i][1]=1;
            if (abs(j)==v[i-1]) dp[i][2]=1;
            if (abs(j-1)==v[i-1]) dp[i][3]=1;
        }
    }
    bool ans=(dp[n-1][2+v[n-1]]||dp[n-1][2-v[n-1]]);
    cout << (ans?"YES":"NO") << '\n';
}
 
int main(){
    ORENOOSHIKYOUMOKAWAIII;
    int _t=1;
    //cin >> _t;
    while(_t--) _solve();
}

:::

### F. Ink Mix
---
#### 題目摘要
#### 想法

:::spoiler 實作

:::

### G. Mobile Robot
---
#### 題目摘要
好好移動機器人們，讓機器人們照編號成等差數列，並使最大移動量最小
#### 想法
將$d\times i-a_i$存起來排序將算最大與最小的差除以二，再把$a$反轉後再做一次

:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ORENOOSHIKYOUMOKAWAIII ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second

template <class T> istream& operator>> (istream& cin, pair<T, T>& tmp){cin >> tmp.F >> tmp.S;return cin;} 
template <class T> istream& operator>> (istream& cin, vector<T>& tmp){for(auto &v:tmp) cin >> v;return cin;}
template <class T> ostream& operator<< (ostream& cout, pair<T, T>& tmp){cout << tmp.F << ' ' << tmp.S;return cout;} 
template <class T> ostream& operator<< (ostream& cout, vector<T>& tmp){for(auto v:tmp) cout << v << ' ';return cout;}

void _solve(){
    int n;
    ll d;
    cin >> n >> d;
    vector<ll> a(n), v(n);
    cin >> a;
    for(int i=0;i<n;i++) v[i]=d*i-a[i];
    sort(v.begin(), v.end());
    ld mid=(v[0]+v.back())/2.0;
    ld ans=(mid-v[0]);
    reverse(a.begin(), a.end());
    for(int i=0;i<n;i++) v[i]=d*i-a[i];
    sort(v.begin(), v.end());
    mid=(v[0]+v.back())/2.0;
    chmin(ans, mid-v[0]);
    cout << fixed << setprecision(1) << ans << '\n';
}

int main(){
    ORENOOSHIKYOUMOKAWAIII;
    int _t=1;
    //cin >> _t;
    while(_t--) _solve();
}

:::

### H. Needle
---
#### 題目摘要
給上中下三條等距直線以及他們上面的一些點，求有多少$\,(u, m, l)\,$使得上中下三點共線

$1 \leq n_u, n_m, n_l \leq 50,000$
$x$-coordinates of the holes are integers between $−30,000$ and $30,000$.
#### 想法
範圍很bitset，不如往bitset想。
然後就發現只要枚舉位移距離後，把上面右移下面左移，及上面左移下面右移
三層答案$\&$起來就好，記得對一條鉛直線的不要重複算。

:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    const int s = 30000;
    bitset<65536> up, down, mid;
    int n; cin >> n;
    rep (i, 0, n) {
        int x; cin >> x;
        up[s + x] = 1;
    }
    int n2; cin >> n2;
    rep (i, 0, n2) {
        int x; cin >> x;
        mid[s + x] = 1;
    }
    int n3; cin >> n3;
    rep (i, 0, n3) {
        int x; cin >> x;
        down[s + x] = 1;
    }
    ll ans = (up & mid & down).count();
    rep (i, 1, s + 1) {
        ans += ((up >> i) & mid & (down << i)).count();
        ans += ((up << i) & mid & (down >> i)).count();
    }
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

:::

### I. Stock Analysis
---
#### 題目摘要
#### 想法

:::spoiler 實作

:::

### J. Switches
---
#### 題目摘要

給一個$N \times N$的矩陣，對每一行$i$詢問需要哪幾行做至多一次的xor操作使得這行剩下$a_{{i}{i}} = 1$。

#### 想法
做高斯消並記錄操作方法
避免算到有操作偶數次的，我對操作方法也做xor
:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    int n; cin >> n;
    vector<int> basis(n, -1);
    vector<bitset<505>> bst;
    rep (i, 0, n) {
        bitset<505> tmp;
        rep (j, 0, n) {
            int a; cin >> a;
            tmp = tmp << 1;
            tmp[0] = a;
        }
        bst.pb(tmp);
    }
    vector<bitset<505>> ope(n);
    rep (i, 0, n) {
        bitset<505> cur;
        cur[i] = 1;
        for (int j = n - 1; j >= 0; --j) if (bst[i][j]) {
            if (basis[j] == -1) {
                basis[j] = i;
                for (int k = j - 1; k >= 0; --k) if (basis[k] != -1) {
                    if (bst[basis[j]][k]) {
                        cur ^= ope[k];
                        bst[i] ^= bst[basis[k]];
                    }
                }
                rep (k, j + 1, n) if (basis[k] != -1) {
                    if (bst[basis[k]][j]) {
                        ope[k] ^= cur;
                        bst[basis[k]] ^= bst[i];
                    }
                }
                ope[j] = cur;
                break;
            } else {
                bst[i] ^= bst[basis[j]];
                cur ^= ope[j];
            }
        }
    }
    rep (i, 0, n) if (basis[i] == -1) {
        cout << -1 << '\n';
        return;
    }
    for (int i = n - 1; i >= 0; --i) {
        rep (j, 0, n) if (ope[i][j]) {
            cout << j + 1 << ' ';
        }
        cout << '\n';
    }
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

:::

### K. Tiling Polyomino
---
#### 題目摘要
給一個無洞並且每個點的鄰居至少會有2個以上的多邊形，問能不能用給定的方塊組成

#### 想法
給定的方塊能把長度為2以上的一行填滿，所以要處理的只有一個的情況，若那格上左右都是豎的，直接把那個變豎的，不然將那格與它下面那格變豎的，給定所有方格要是橫的還豎的，接下來只要跑橫的與豎的判一槓長度奇偶構造就好

:::spoiler 實作

#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second

const int N=1005;
char a[N][N];
char ans[N][N];

void _solve(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin >> a[i][j];
    for(int i=0;i<=n+1;i++) a[i][0]=a[i][n+1]=a[0][i]=a[n+1][i]='0';
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if (a[i][j]=='1'&&a[i][j-1]!='1'&&a[i][j+1]!='1'){
        a[i][j]='2';
        if (a[i-1][j]!='2'||a[i][j-1]!='2'||a[i][j+1]!='2'){
            a[i+1][j]='2';
        }
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if (a[i][j]=='0') ans[i][j]='0';
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if (a[i][j]=='1'){
        int k=j;
        while(a[i][k]=='1') ans[i][k++]='2';
        if ((k-j)&1) ans[i][j]=ans[i][j+1]=ans[i][j+2]='4';
        j=k;
    }
    for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) if (a[i][j]=='2'){
        int k=i;
        while(a[k][j]=='2') ans[k++][j]='3';
        if ((k-i)&1) ans[i][j]=ans[i+1][j]=ans[i+2][j]='5';
        i=k;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cout << ans[i][j];
        cout << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    //cin >> _t;
    while(_t--) _solve();
}

:::

### L. Two Buildings
---
#### 題目大綱
給一陣列$h$，求$\max_{1 \leq i < j \leq n} (h_i + h_j) \ast (j − i)$
#### 想法
將所有$h_i$看作二維平面的$(i, h_i)$，複製一份$(i, -h_i)$在下面，可以發現這就是不單調的[超大畫框設置](https://tioj.ck.tp.edu.tw/problems/1283)問題，因此先對上面的點保留$y$軸嚴格遞減的點，確保轉移點的單調性，之後就直接套轉移點單調的優化就好。
:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    int n; cin >> n;
    vector<pll> a, b;
    vector<ll> y(n);
    rep (i, 0, n) {
        ll x; cin >> x;
        y[i] = -x;
        while (!a.empty() && x >= a.back().F) a.pop_back();
        a.pb({x, i});
    }
    int m = a.size();
    auto calc = [&](int i, int j) -> ll {
        return (a[j].F - y[i]) * (a[j].S - i);
    };
    ll ans = 0;
    auto dc = [&](auto self, int l, int r, int ql, int qr) -> void {
        if (l > r) return;
        if (ql == qr) {
            rep (i, l, r + 1) {
                chmax(ans, calc(ql, i));
            }
            return;
        }
        int mid = l + r >> 1, opt;
        ll res = -1;
        rep (i, ql, qr + 1) {
            if (chmax(res, calc(i, mid))) {
                opt = i;
            }
        }
        chmax(ans, res);
        self(self, l, mid - 1, ql, opt);
        self(self, mid + 1, r, opt, qr);
    };
    dc(dc, 0, m - 1, 0, n - 1);
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

:::