#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;
}
/*
*/

Для того чтобы решить эту задачу, давайте воспользуемся следующим жадным алгоритмом.

Отсортируем цены плиток шоколада по возрастанию, после чего будем идти слева направо и брать шоколадки, которые имеют цену не меньшую, чем $$$l$$$, но не большую, чем $$$r$$$ до тех пор, пока у нас не закончатся деньги.

Количество плиток шоколада, которые мы взяли, и будет являться ответом на задачу.

Итоговая асимптотика по времени: $$$\mathcal{O}(n\log{}n)$$$.

Очевидно, что чем более часто мы должны ходить в $$$i$$$ здание, тем более близко оно должно быть к главному офису.

Из этого следует жадный алгоритм. Давайте поставим главный офис в точку $$$0$$$, а все остальные отсортируем по $$$a_i$$$. Тогда самое посещаемой здание поставим в точку с координатой $$$1$$$, второй по частоте в $$$-1$$$, третье в $$$2$$$ и т.д.

Итоговая асимптотика по времени: $$$\mathcal{O}(n\log{}n)$$$.

Давайте для каждого бита посчитаем, сколько раз он войдёт в ответ.

Пусть мы рассматриваем сейчас $$$i$$$-й бит. Заметим, что если ни одно число не содержит в себе включённый $$$i$$$-й бит, то такой бит ни разу не войдёт в ответ. В противном случае, в каждую из подпоследовательностей $$$i$$$-й бит входит либо чётное количество раз, либо нечётное. Если бит входит чётное количество раз, то мы не должны считать такую подпоследовательность, потому что побитовое исключающее ИЛИ по этому биту будет равно нулю. Если же бит входит нечётное количество раз, то мы должны посчитать такую подпоследовательность, потому что побитовое исключающее ИЛИ по этому биту будет равно единице.

Утверждается, что количество подпоследовательностей, в которые $$$i$$$-й бит входит нечётное количество раз, равно в точности $$$2^{n - 1}$$$. Докажем это.

Разделим числа на два множества $$$A$$$ и $$$B$$$. В множестве $$$A$$$ будут числа, у которых $$$i$$$-й бит выключен, в множестве $$$B$$$ числа, у которых $$$i$$$-й бит включён.

Заметим, что числа из множества $$$A$$$ никак не влияют на ответ, потому что $$$x \; XOR \; 0 = 1$$$. Таким образом, какое бы подмножество из $$$A$$$ мы ни взяли, $$$i$$$-й бит не изменит своей чётности. Всего таких подмножеств будет $$$2^{|A|}$$$.

Положим $$$k = 1$$$, если $$$|B|$$$ чётно или $$$k = 0$$$, если $$$|B|$$$ нечётно. Для того, чтобы $$$i$$$-й бит входил в подпоследовательность нечётное количество раз, нужно взять нечётное количество элементов из множества $$$B$$$. Это количество равно $$$C_{|B|}^{1} \, + \, C_{|B|}^{3} \, + \dots \, + \, C_{|B|}^{|B| - k} = 2^{|B| - 1}$$$.

Таким образом, $$$i$$$-й бит включён ровно в $$$2^{|A|} \cdot 2^{|B| - 1} = 2^{n - 1}$$$ подпоследовательностях, что и требовалось доказать.

Имея ввиду полученный выше факт, реализация решения этой задачи получается весьма и весьма лаконичной: если положить $$$x$$$ равное побитовому ИЛИ всех элементов последовательности (или, что то же самое, ИЛИ всех заданных отрезков), то ответ будет равен $$$x \cdot 2^{n - 1}$$$ по модулю $$$10^9 + 7$$$.

Итоговая асимптотика по времени: $$$\mathcal{O}(n)$$$.

Будем решать задачу методом динамического программирования. Пусть $$$dp_i$$$ максимальный ответ для всех массивов, конечный элемент которых делится на $$$i$$$. Давайте считать динамику от $$$C$$$ до $$$1$$$, где $$$C$$$ — максимальное значение $$$a_i$$$. Изначально $$$dp_i = cnt_i \cdot i$$$, где $$$cnt_i$$$ — количество $$$a_i = i$$$. Как пересчитывать наше динамическое программирование? $$$dp_i = max(dp_i, dp_j + i \cdot (cnt_i - cnt_j))$$$, для всех таких $$$j$$$, что $$$j$$$ $$$mod$$$ $$$i = 0$$$ (т.е. $$$j$$$ делится $$$i$$$). В этой динамике мы перебираем прошлое изменение нашего $$$gcd$$$ на префиксе, и жадно дописываем все возможные элементы.

Итоговая асимптотика по времени $$$\mathcal{O}(C\log{}C)$$$.

Для решения $$$D2$$$ заметим, что для пересчета динамики мы можем перебирать все такие $$$j$$$, которые отличаются от $$$i$$$ умножением ровно на $$$1$$$ простое число. Также для ускорения решения мы можем использовать линейное решето Эратосфена для нахождения простых чисел и факторизации.

Итоговая асимптотика по времени: $$$\mathcal{O}(C\log{}\log{}C)$$$.

Пусть $$$ans_{temp}$$$ — это текущий ответ для температуры $$$temp$$$. До начала всех действий $$$ans_{temp}$$$ считается равным $$$temp$$$.

Для того чтобы отвечать на очередной запрос с температурой $$$x$$$, нам нужно будет просто выводить значение $$$ans_x$$$. Но как поддерживать $$$ans$$$? С помощью неявного дерева отрезков, в вершинах которого будут хранится минимум, максимум, а также переменная $$$add$$$, в которой будет находится значение, которое надо прибавить к текущей вершине (то есть это такая вспомогательная переменная, которая нужна для осуществления ленивых операций на дереве отрезков).

В начале очередного дня приходит температура $$$T$$$. Теперь нам нужно изменить текущий ответ для некоторых $$$temp$$$. Нам нужно найти такие $$$ans_{temp}$$$, что $$$ans_{temp} < T$$$ и прибавить к ним $$$+1$$$, а затем найти такие $$$ans_{temp}$$$, что $$$ans_{temp} > T$$$ и прибавить к ним $$$-1$$$. Всё это сделать нетрудно, просто запускаясь из корня дерева отрезков и останавливаясь в моменты, когда:

• максимум текущей вершины меньше, чем $$$T$$$ — здесь мы прибавляем $$$+1$$$;
• минимум текущей вершины больше, чем $$$T$$$ — здесь мы прибавляем $$$-1$$$;
• минимум вершины равен максимуму вершины (а, значит, и самому $$$T$$$) — здесь мы ничего не прибавляем.

Итоговая асимптотика по времени: $$$\mathcal{O}(n\log{}T)$$$.