Znzryb's Blog

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = long long;
using ull = unsigned long long;
using ld = double;
using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<ld>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        __();
    return 0;
}
/*

*/
ll binpow(ll a, ll k) {
    a %= mod;
    ll res = 1;
    if (k < 0)
        return 1;
    while (k) {
        if (k & 1) {
            res *= a;
            res %= mod;
        }
        k >>= 1;
        a *= a;
        a %= mod;
    }
    return res;
}
inline void __() {
    cin >> N;
    vll A(N + 5);
    FOR(i, 1, N) { cin >> A[i]; }
    sort(A.begin() + 1, A.begin() + N + 1);
    ll ans = 0;
    ll inv2 = binpow(2, mod - 2);
    FOR(i, 2, N) {
        ll lans = 0;
        lans = binpow(2, N - i) * (binpow(3, i - 1) - 1);
        lans %= mod;
        lans *= inv2;
        lans %= mod;
        lans *= A[i];
        lans %= mod;
        ans += lans;
        ans %= mod;
    }
    // #ifdef LOCAL
    //     cerr << "OK/n";
    // #endif
    FOR(i, 1, N) {
        ll lans = binpow(2, N - i) * A[i];
        lans %= mod;
        ans += lans;
        ans %= mod;
    }
    ans %= mod;
    if (ans < 0)
        ans += mod;
    cout << ans << "\n";
}
/*
AC
https://qoj.ac/submission/1345581
*/

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<ld>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*

*/
ll a,b,c,ab,ac,bc,abc;
bool check(ll mid){
    if(a+ac+ab+abc<mid) return false;
    if(b+bc+ab+abc<mid) return false;
    if(c+bc+ac+abc<mid) return false;
    if(a+c+ab+ac+bc+abc<2*mid) return false;
    if(a+b+ab+ac+bc+abc<2*mid) return false;
    if(b+c+ab+ac+bc+abc<2*mid) return false;
    if(N/3<mid) return false;
    return true;
}
inline void __(){
    cin>>N;
    cin>>a>>b>>ab>>c>>ac>>bc>>abc;
    ll l=0,r=N;
    while (l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    cout<<l<<"\n";
}
/*
AC
https://vjudge.net/solution/63690535
*/

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<ld>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)2e5+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*
通过打表，我们发现这个通过最大值和这个长度，我们可以唯一确定一个序列。

*/
ll Pos[MAXN];
inline void __(){
    cin>>N;
    vll A(N+5);
    FOR(i,1,N){
        cin>>A[i];
        Pos[A[i]]=i;
    }
    ll id=max(A[1],A[N]);
    ll ans=0;
    // 通过打表，我们发现这个通过最大值和这个长度，我们可以唯一确定一个序列。
    vll pre(N+5,INF),suf(N+5,INF);
    FOR(i,1,N){
        pre[i]=min(pre[i-1],A[i]);
    }
    ROF(i,N,1){
        suf[i]=min(suf[i+1],A[i]);
    }
    FOR(i,1,N){
        if(i==N){
            // 如果说这个 i 是 N，在中间的话就就会直接被删掉 
            if(Pos[i]==1 || Pos[i]==N){
                ans+=N;
            }else{
                ans++;
            }
            continue;
        }
        if(i==1 || i==2){
            ans+=i;
            continue;
        }
        if(i<=suf[Pos[i]] || i<=pre[Pos[i]]){
            ans+=i;
        }else{
            ans++;
        }
    }
    ans%=mod;
    cout<<ans<<"\n";
    // ROF(i,N,1){
    //     if(Pos[i]==1 && Pos[i]==N){
    //         id=i;
    //         break;
    //     }
    // }

    
}
/*
AC
https://www.codechef.com/viewsolution/1191801507
1
4
1 3 2 4


[ 1 ]: 2
[ 1 2 ]: 1
[ 2 ]: 1
[ 3 ]: 1
[ 3 1 ]: 1
[ 3 1 2 ]: 1
[ 3 1 4 2 ]: 1
最大值为：1 的长度为：1 的东西：1
最大值为：2 的长度为：1 的东西：1
最大值为：2 的长度为：2 的东西：1
最大值为：3 的长度为：1 的东西：1
最大值为：3 的长度为：2 的东西：1
最大值为：3 的长度为：3 的东西：1
最大值为：4 的长度为：4 的东西：1



*/