#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, a[N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i = 0 ; i < n ; ++i)
            scanf("%d", a + i);
    
        sort(a, a + n);
    
        if(a[0] == a[n - 1]){
            printf("%lld\n", (1LL * n * (n - 1LL)));
            continue;
        }
    
        int mn = 0, mx = n - 1;
    
        while(a[0] == a[mn])
            ++mn;
    
        while(a[n - 1] == a[mx])
            --mx;
    
        long long l = mn;
        long long r = n - mx - 1;
    
    
        printf("%lld\n", 2LL * l * r);
    }
}

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e5 + 5, M = 1e5 + 5;

int n, m;
int mn[N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        for(int i = 1 ; i <= n ; ++i)
            mn[i] = n;
    
        for(int i = 0 ; i < m ; ++i){
            int x, y;
            scanf("%d %d", &x, &y);
            
            if(x > y)
                swap(x, y);
                
            mn[x] = min(mn[x], y - 1);
        }
    
        for(int i = n - 1 ; i ; --i)
            mn[i] = min(mn[i], mn[i + 1]);
    
        ll ans = n;
        for(int i = 0 ; i < n ; ++i)
            ans += (mn[i] - i);
    
        printf("%lld\n", ans);
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 2 * N + 5;

bool vis[N], ans;

void Sieve(){
    memset(vis, true, sizeof(vis));
    
    vis[0] = vis[1] = false;
    for(int i = 4 ; i < N ; i += 2)
        vis[i] = false;
    for(int i = 3 ; i < N / i ; i += 2){
        if(!vis[i])continue;
        for(int j = i * i ; j < N ; j += i + i)
            vis[j] = false;
    }
}

int in[N], vid;
vector<int> primes;

void Gen(){
    for(int i = 2 ; i < N ; ++i)
        if(vis[i])
            primes.emplace_back(i);
}

set<int> st;

void check(int x){
    if(in[x] == vid){
        ans = true;
        return;
    }

    in[x] = vid;
}

void fact(int x){

    if(x < N && vis[x] == true){
        check(x);
        return;
    }

    int idx = 0, sz = primes.size();

    while(x > 1 && idx < sz && x / primes[idx] >= primes[idx]){

        if(x % primes[idx] == 0){
            check(primes[idx]);
            while(x % primes[idx] == 0)x /= primes[idx];
        }

        ++idx;
    }

    if(x > 1){
        if(x < N)
            return check(x), void();

        if(st.find(x) != st.end()){
            ans = true;
            return;
        }

        st.emplace(x);
    }
}

void pre(){
    ++vid;
    st.clear();
}

int main(){
    Sieve();
    Gen();

    int t;
    scanf("%d", &t);
    while(t--){
        pre();
        
        int n;
        scanf("%d", &n);
        
        ans = false;
        
        while(n--){
            int x;
            scanf("%d", &x);
            fact(x);
        }
        
        puts(ans ? "YES" : "NO");
    }
    
}

#include <bits/stdc++.h>

using namespace std;

void dfs(int v, vector<vector<int>> &g, vector<vector<int>> &go, vector<vector<pair<int, int>>> &kek, int s, int t = -1, int p = -1, int len = 0){
    if(len == 1)
        t = v;

    if(len > 1)
        go[s][v] = t;

    kek[len].push_back({s, v});

    for(int u : g[v])
        if(u != p)
            dfs(u, g, go, kek, s, t, v, len + 1);
}

void Solve(){
    int n; cin >> n;
    string a; cin >> a;

    vector<vector<int>> g(n);
    vector<vector<int>> go(n, vector<int>(n));
    vector<vector<pair<int, int>>> kek(n);
    vector<vector<int>> dp(n, vector<int>(n));

    for(int i = 0; i < n - 1; i++){
        int v, u;
        cin >> v >> u;
        g[--v].push_back(--u);
        g[u].push_back(v);
    }

    for(int v = 0; v < n; v++)
        dfs(v, g, go, kek, v);

    for(int len = 0; len < n; len++){
        for(auto p : kek[len]){
            int v = p.first;
            int u = p.second;

            if(len == 0){
                dp[v][u] = 1;
            }else if(len == 1){
                dp[v][u] = 1 + (a[v] == a[u]);
            }else{
                int x = dp[v][go[u][v]];
                int y = dp[go[v][u]][u];
                int z = dp[go[v][u]][go[u][v]] + ((a[v] == a[u]) << 1);
                dp[v][u] = max({x, y, z});
            }
        }
    }

    int ans = 0;

    for(int v = 0; v < n; v++)
        for(int u = 0; u < n; u++)
            ans = max(ans, dp[v][u]);

    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    int test = 1;
    cin >> test;
 
    for(int i = 1; i <= test; i++)
        Solve();
}

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;

const int N = 4e2 + 5;

int n, m;
char a[N][N];

int upM[N][N];
int upB[N][N];

int downM[N][N];
int downB[N][N];

int _get(int I, int j, int incI, char ch){
    int i = I + incI;

    while(i >= 0 && i < n){
        if(a[i][j] == '#')
            break;

        if(a[i][j] == ch)
            break;

        i += incI;
    }

    return i;
}

int _getCount(int i, int j){
    if(a[i][j] == 'm')
        return 1;

    return (a[i][j] == '.' ? 0 : 10);
}

/**

1  2    4  8
UL DL   UR DR

*/


int getU(int i, int j, int bt){
    if(!bt)
        return max(upM[i][j], upB[i][j]) + 1;

    int cur = upM[i][j];

    if(cur == -1 || a[cur][j] == '#')
        return cur + 1;

    cur = upM[cur][j];

    return cur + 1;
}


int getD(int i, int j, int bt){
    if(!bt)
        return min(downM[i][j], downB[i][j]) &mdash; 1;

    int cur = downM[i][j];

    if(cur == n || a[cur][j] == '#')
        return cur - 1;

    cur = downM[cur][j];

    return cur - 1;
}


int solve(int i, int l, int r, int msk){
    int upL = getU(i, l, (msk & 1));
    int downL = getD(i, l, (msk & 2));


    int upR = getU(i, r, (msk & 4));
    int downR = getD(i, r, (msk & 8));


    int up = max(upL, upR);
    int down = min(downL, downR);

    if(up < i && down > i)
        return  2 * (down - up + 1) + (r - l - 1);
    
    return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    scanf("%d %d", &n, &m);
    for(int i = 0 ; i < n ; ++i)
        scanf("%s", a + i);

    for(int i = 0 ; i < n ; ++i){
        for(int j = 0 ; j < m ; ++j){
            if(a[i][j] == '#')
                continue;

            upM[i][j] = _get(i, j, -1, 'm');
            upB[i][j] = _get(i, j, -1, '#');

            downM[i][j] = _get(i, j, 1, 'm');
            downB[i][j] = _get(i, j, 1, '#');
        }
    }

    int mx = 0;
    for(int i = 0 ; i < n ; ++i){
        for(int j = 0 ; j + 2 < m ; ++j){

            int cnt = _getCount(i, j) + _getCount(i, j + 1);
            for(int k = j + 2 ; k < m ; ++k){
                if((cnt += _getCount(i, k)) > 1)
                    break;

                mx = max(mx, solve(i, j, k, 0));

                if(cnt == 1)
                    continue;

                mx = max(mx, solve(i, j, k, 1));
                mx = max(mx, solve(i, j, k, 2));
                mx = max(mx, solve(i, j, k, 4));
                mx = max(mx, solve(i, j, k, 8));
            }

        }
    }

    printf("%d\n", mx);
}

#include <bits/stdc++.h>

using namespace std;

const int p1 = 31;
const int p2 = 53;

unsigned long long pow1[32];
unsigned long long pow2[32];

struct Node{
    unsigned long long hsh = 0;
    Node *l = 0, *r = 0;
    bool was = false;
};

const int max_memory = 13e7;

int pos_memory = 0;
char memory[max_memory];
 
void* operator new(size_t n) {
    char *res = memory + pos_memory;
    pos_memory += n;
    assert(pos_memory <= max_memory);
    return (void*) res;
}
 
void operator delete(void *){}

Node * upd(Node *v, unsigned long long x, int i = 18){
    if(i == -1){
        Node *u = new Node();

        if(!v || v && !v->was){
            u->hsh = ((int(1e9) + 345) ^ x) * (3 * x + 654);
            u->was = true;
        }

        return u;
    }

    if(x & (1 << i)){
        Node *res = new Node();
        res->l = (v ? v->l : 0);
        res->r = upd((v ? v->r : 0), x, i - 1);
        unsigned long long a = (res->l ? res->l->hsh * pow1[i + 1] : 0);
        unsigned long long b = (res->r ? res->r->hsh * pow2[i + 1] : 0);
        res->hsh = a + b;
        return res;
    }else{
        Node *res = new Node();
        res->l = upd((v ? v->l : 0), x, i - 1);
        res->r = (v ? v->r : 0);
        unsigned long long a = (res->l ? res->l->hsh * pow1[i + 1] : 0);
        unsigned long long b = (res->r ? res->r->hsh * pow2[i + 1] : 0);
        res->hsh = a + b;
        return res;
    }
}

int get(Node *l, Node *r, int i = 18, int now = 0){
    if((l ? l->hsh : 0) == (r ? r->hsh : 0))
        return -1;

    if(i == -1)
        return now;

    if((l && l->l ? l->l->hsh : 0) == (r && r->l ? r->l->hsh : 0))
        return get((l ? l->r : 0), (r ? r->r : 0), i - 1, now + (1 << i));

    return get((l ? l->l : 0), (r ? r->l : 0), i - 1, now);
}

void Solve(){
    pow1[0] = 1;
    pow2[0] = 1;

    for(int i = 1; i <= 31; i++){
        pow1[i] = p1 * pow1[i - 1];
        pow2[i] = p2 * pow2[i - 1];
    }

    int n; cin >> n;
    vector<pair<int, int>> a(n);
    vector<int> mp(n + 1);

    {
        for(int i = 0; i < n; i++){
            cin >> a[i].first;
            a[i].second = i;
        }

        sort(a.begin(), a.end());
        map<int, int> kek;
        int now = 0;

        for(int i = 0; i < n; i++){
            if(a[i].first != (i ? a[i - 1].first : -1))
                now++;

            kek[a[i].first] = now;
        }

        sort(a.begin(), a.end(), [](pair<int, int> x, pair<int, int> y){ return x.second < y.second; });

        for(int i = 0; i < n; i++){
            int x = kek[a[i].first];
            mp[x] = a[i].first;
            a[i].first = x;
        }
    }

    vector<Node *> t(n + 1);

    t[0] = new Node();

    for(int i = 1; i <= n; i++){
        int x = a[i - 1].first;
        t[i] = upd(t[i - 1], x);
    }

    int q; cin >> q;
    
    int last = 0;

    while(q--){
        int a, b;
        cin >> a >> b;

        int l = (last ^ a);
        int r = (last ^ b);

        int kek = get(t[l - 1], t[r]);
        int ans = (kek != -1 ? mp[kek] : 0);
        cout << ans << '\n';
        last = ans;
    }
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    Solve();
}

#pragma optimize("SEX_ON_THE_BEACH")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("unroll-all-loops")
#pragma GCC optimize("O3")
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
//#define _FORTIFY_SOURCE 0 
#pragma GCC optimize("no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") 

#include<bits/stdc++.h>
#include <x86intrin.h>

using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;
using dd = double;
using ldd = long double;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using pdd = std::pair<dd, dd>;
using pld = std::pair<ldd, ldd>;

namespace fast {
    template<typename T>
    T gcd(T a, T b) {
        return gcd(a, b);
    }

    template<>
    unsigned int gcd<unsigned int>(unsigned int u, unsigned int v) {
        int shift;
        if (u == 0)
            return v;
        if (v == 0)
            return u;
        shift = __builtin_ctz(u | v);
        u >>= __builtin_ctz(u);
        do {
            unsigned int m;
            v >>= __builtin_ctz(v);
            v -= u;
            m = (int)v >> 31;
            u += v & m;
            v = (v + m) ^ m;
        } while (v != 0);
        return u << shift;
    }

    template<>
    unsigned long long gcd<unsigned long long>(unsigned long long u, unsigned long long v) {
        int shift;
        if (u == 0)
            return v;
        if (v == 0)
            return u;
        shift = __builtin_ctzll(u | v);
        u >>= __builtin_ctzll(u);
        do {
            unsigned long long m;
            v >>= __builtin_ctzll(v);
            v -= u;
            m = (long long)v >> 63;
            u += v & m;
            v = (v + m) ^ m;
        } while (v != 0);
        return u << shift;
    }
}
 
namespace someUsefull {
    template<typename T1, typename T2>
    inline void checkMin(T1& a, T2 b) {
        if (a > b)
            a = b;
    }
 
    template<typename T1, typename T2>
    inline void checkMax(T1& a, T2 b) {
        if (a < b)
            a = b;
    }

    template<typename T1, typename T2>
    inline bool checkMinRes(T1& a, T2 b) {
        if (a > b) {
            a = b;
            return true;
        }
        return false;
    }

    template<typename T1, typename T2>
    inline bool checkMaxRes(T1& a, T2 b) {
        if (a < b) {
            a = b;
            return true;
        }
        return false;
    }
}
 
namespace operators {
    template<typename T1, typename T2>
    std::istream& operator>>(std::istream& in, std::pair<T1, T2>& x) {
        in >> x.first >> x.second;
        return in;
    }
 
    template<typename T1, typename T2>
    std::ostream& operator<<(std::ostream& out, std::pair<T1, T2> x) {
        out << x.first << " " << x.second;
        return out;
    }
 
    template<typename T1>
    std::istream& operator>>(std::istream& in, std::vector<T1>& x) {
        for (auto& i : x) in >> i;
        return in;
    }
 
    template<typename T1>
    std::ostream& operator<<(std::ostream& out, std::vector<T1>& x) {
        for (auto& i : x) out << i << " ";
        return out;
    }
}
 
//name spaces
using namespace std;
using namespace operators;
using namespace someUsefull;
//end of name spaces
 
//defines
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define NO {cout << "NO"; return;}
#define YES {cout << "YES"; return;}
 
//end of defines
//#undef HOME
//debug defines
#ifdef HOME
    #define debug(x) cerr << #x << " " << (x) << endl;
    #define debug_v(x) {cerr << #x << " "; for (auto ioi : x) cerr << ioi << " "; cerr << endl;}
    #define debug_vp(x) {cerr << #x << " "; for (auto ioi : x) cerr << '[' << ioi.ff << " " << ioi.ss << ']'; cerr << endl;}
    #define debug_v_v(x) {cerr << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cerr << ioi2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;}
    int jjj;
    #define wait() cin >> jjj;
    #define PO cerr << "POMELO" << endl;
    #define OL cerr << "OLIVA" << endl;
    #define gen_clock(x) cerr << "Clock " << #x << " created" << endl; ll x = clock(); 
    #define check_clock(x) cerr << "Time spent in " << #x << ": " << clock() - x << endl; x = clock();
    #define reset_clock(x) x = clock();
    #define say(x) cerr << x << endl;
#else
    #define debug(x) 0;
    #define debug_v(x) 0;
    #define debug_vp(x) 0;
    #define debug_v_v(x) 0;
    #define wait() 0;
    #define PO 0;
    #define OL 0;
    #define gen_clock(x) 0;
    #define check_clock(x) 0;
    #define reset_clock(x) 0;
    #define say(x) 0;
#endif // HOME

const int SIZE = 200000;
const int block = 64;
const int _size = (SIZE + 63) / 64;

struct bs {
    ull arr[_size];

    bs() {
        for (int i = 0; i < _size; ++i) arr[i] = 0;
    }

    bs& operator^=(bs &other) {
        #pragma GCC ivdep
        for (int i = 0; i < _size; ++i)
            arr[i] ^= other.arr[i];
        return *this;
    }

    int _Find_first_in_xor(bs& other) {
        ull t;
        for (int i = 0; i < _size; ++i) {
            if (t = arr[i] ^ other.arr[i]) {
                return (i << 6) + __builtin_ctzll(t);
            }
        }
        return SIZE;
    }

    int _Find_first() {
        for (int i = 0; i < _size; ++i) {
            if (arr[i]) {
                return (i << 6) + __builtin_ctzll(arr[i]);
            }
        }
        return SIZE;
    }

    void flip(int id) {
        ull &x = arr[id >> 6];
        id &= 63;
        x ^= ((ull)1 << id);
    }

    int size() {
        return SIZE;
    }

};


ostream& operator<<(ostream &os, bs &x) {
    for (int i = 0; i < _size; ++i) {
        os << x.arr[i] << " ";
    }
    return os;
}

void solve(int test) {
    int n;
    cin >> n;
    vector<int> arr(n);
    cin >> arr;
    vector<int> to(n);
    {
        map<int, int> have;
        for (int i : arr) have[i] = 0;
        int cnt = 0;
        for (auto &i : have) {
            i.ss = cnt;
            to[cnt] = i.ff;
            cnt++;
        }
        for (int &i: arr) i = have[i];
    }

    vector<vector<int>> blocks;
    for (int i = 0; i < n; i += block) {
        blocks.push_back({});
        for (int j = 0; i + j < n && j < block; ++j) {
            blocks.back().push_back(arr[i + j]);
        }
    }

    vector<bs> blocks_bs(blocks.size());
    for (int i = 0; i < blocks.size(); ++i) {
        for (int j : blocks[i]) {
            blocks_bs[i].flip(j);
        }
    }
    for (int i = 1; i < blocks.size(); ++i) {
        blocks_bs[i] ^= blocks_bs[i - 1];
    }

    int q;
    cin >> q;
    bs have;
    int last = 0;
    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;

        int l = (last ^ a);
        int r = (last ^ b);

        // cin >> l >> r;
        --l;
        --r;
        int lb = l / block;
        int rb = r / block;
        if (rb - lb <= 1) {
            int L = l;
            while (l <= r) {
                have.flip(arr[l]);
                ++l;
            }
            int id = have._Find_first();

            int ans = (id == have.size() ? 0 : to[id]);
            last = ans;
            cout << ans << '\n';
            l = L;
            while (l <= r) {
                have.flip(arr[l]);
                ++l;
            }
        } else {
            int L = (lb + 1) * block;
            int old_l = l;
            int R = (rb + 1) * block;
            checkMin(R, n);
            int old_r = r;
            ++r;
            while (r < R) {
                blocks_bs[rb].flip(arr[r]);
                ++r;
            }
                        while (l < L) {
                blocks_bs[lb].flip(arr[l]);
                ++l;
            }
            int id = blocks_bs[rb]._Find_first_in_xor(blocks_bs[lb]);
            int ans = (id == have.size() ? 0 : to[id]);
            last = ans;
            cout << ans << '\n';
            r = old_r;
            ++r;
            while (r < R) {
                blocks_bs[rb].flip(arr[r]);
                ++r;
            }
            l = old_l;
            while (l < L) {
                blocks_bs[lb].flip(arr[l]);
                ++l;
            }
        }
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
 
    int t = 1;
    //cin >> t;
    for (int i = 0; i < t; ++i) {
        solve(i+1);
        //cout << '\n';
        //PO;
    }
    return 0;
}
/*
*/

To solve this problem, let's use the following greedy algorithm.

Let's sort the prices of chocolate bars in increasing order, after which we will go from left to right and take chocolates that have a price not less than $$$l$$$, but not more than $$$r$$$ until we run out of money.

The number of chocolate bars that we took will be the answer to the problem.

The resulting asymptotics in time: $$$\mathcal{O}(n\log{}n)$$$.

Obviously, the more often we have to go to the $$$ i $$$ building, the closer it should be to the main office.

This implies a greedy algorithm. Let's put the main office at $$$0$$$ and sort the rest by $$$a_i$$$. Then we put the most visited building at a point with a coordinate of $$$1$$$, the second at $$$-1$$$, the third at $$$2$$$, etc.

The resulting asymptotics in time is $$$\mathcal{O}(n\log{}n)$$$.

Let's count for each bit how many times it will be included in the answer.

Let us now consider the $$$i$$$-th bit. Note that if no number contains the included $$$i$$$-th bit, then such a bit will never be included in the answer. Otherwise, each of the subsequences contains $$$i$$$-th bit even or odd number of times. If a bit enters an even number of times, then we should not count such a subsequence, because the bitwise exclusive OR for this bit will be zero. If the bit enters an odd number of times, then we must count such a subsequence, because the bitwise exclusive OR for this bit will be equal to one.

It is stated that the number of subsequences in which the $$$i$$$-th bit enters an odd number of times is equal to $$$2^{n - 1}$$$. Let's prove it.

Divide the numbers into two sets $$$A$$$ and $$$B$$$. In the set $$$A$$$ there will be numbers whose $$$i$$$th bit is off, in the set $$$B$$$ there will be numbers whose $$$i$$$-th bit is on.

Note that the numbers from the set $$$A$$$ do not affect the answer in any way, because $$$x\; XOR\; 0 = 1$$$. Thus, whichever subset of $$$A$$$ we take, the $$$i$$$-th bit will not change its parity. There will be $$$2^{|A|}$$$ in total of such subsets.

Let $$$k = 1$$$ if $$$|B|$$$ is even, or $$$k = 0$$$ if $$$|B|$$$ is odd. In order for the $$$i$$$-th bit to enter the subsequence an odd number of times, you need to take an odd number of elements from the set $$$B$$$. This number is equal to $$$C_{|B|}^{1} \, + \, C_{|B|}^{3} \, + \dots \, + \, C_{|B|}^{|B| - k} = 2^{|B| - 1}$$$.

Thus, the $$$i$$$-th bit is included in exactly $$$2^{|A|}\cdot 2^{|B|- 1}= 2^{n - 1}$$$ subsequences, which was required to be proved.

Then the solution to this problem turns out to be very simple: let $$$x$$$ be equal to the bitwise OR of all elements of the sequence (or, the same thing, bitwise OR of all given segments), then the answer will be equal to $$$x\cdot 2^{n - 1}$$$ modulo $$$10^9 + 7$$$.

The resulting asymptotics in time: $$$\mathcal{O}(n)$$$.

Let's solve the dynamic programming problem. Let $$$dp_i$$$ be the maximum answer for all arrays, the last element of which is divisible by $$$i$$$. Let's calculate the dynamics from $$$C$$$ to $$$1$$$, where $$$C$$$ is the maximum value of $$$a_i$$$. Initially, $$$dp_i = cnt_i \cdot i$$$, where $$$cnt_i$$$ is the amount of $$$a_i = i$$$. How do we recalculate our dynamic programming? $$$dp_i = max(dp_i, dp_j + i \cdot (cnt_i - cnt_j))$$$, for all $$$j$$$ such that $$$j$$$ $$$mod$$$ $$$i = 0$$$ (i.e. $$$j$$$ is divisible by $$$i$$$). In this dynamic, we iterate over the past change of our $$$gcd$$$ on the prefix, and greedily add all possible elements.

The resulting asymptotics in time is $$$\mathcal{O}(C\log{}C)$$$.

To solve $$$D2$$$, we can notice that to recalculate the dynamics, we can iterate over all such $$$j$$$ that differ from $$$i$$$ by multiplying exactly $$$1$$$ prime number. Also, to speed up the solution, we can use the linear sieve of Eratosthenes to find primes and factorization.

The resulting asymptotics in time: $$$\mathcal{O}(C\log{}\log{}C) $$$.

Let $$$ans_{temp}$$$ the current answer for temperature $$$temp$$$. Before all days, $$$ans_{temp}$$$ is considered equal to $$$temp$$$.

In order to respond to a request with a temperature of $$$x$$$, we will just need to output the value of $$$ans_x$$$. But how to maintain $$$ans$$$? With the help of an implicit tree of segments, at the vertices of which the minimum and maximum will be stored, as well as the variable $$$add$$$, which will contain the value that needs to be added to the current vertex (that is, such a variable that is needed to perform lazy operations on the segment tree).

At the beginning of the next day you get the temperature $$$T$$$. Now we need to change the current answer for some $$$temp$$$. We need to find such $$$ans_{temp}$$$ that $$$ans_{temp} <T$$$ and add $$$+1$$$ to them, and then find such $$$ans_{temp}$$$ that $$$ans_{temp} > T$$$ and add $$$-1$$$ to them. All this is not difficult to do, just starting from the root of the segment tree and stopping at the moments when:

• the maximum of the current vertex is less than $$$T$$$ — here we add $$$+1$$$;
• the minimum of the current vertex is greater than $$$T$$$ — here we add $$$-1$$$;
• the minimum of the vertex is equal to the maximum of the vertex (and, therefore, the $$$T$$$ itself) — here we do not add anything.

The resulting asymptotics in time: $$$\mathcal{O}(n\log{}T)$$$.