結果

問題 No.2250 Split Permutation
ユーザー 👑 p-adic
提出日時 2023-06-29 12:14:26
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 56 ms / 3,000 ms
コード長 34,797 bytes
コンパイル時間 12,979 ms
コンパイル使用メモリ 294,248 KB
最終ジャッジ日時 2025-02-15 03:03:10
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort )
#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
#define CERR( ANSWER ) cerr << ANSWER << endl;
#define COUT( ANSWER ) cout << ANSWER << endl
#define ASSERT( A , MIN , MAX ) CERR( "ASSERT " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << (
      MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
#define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
#else
#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
#define CERR( ANSWER )
#define COUT( ANSWER ) cout << ANSWER << "\n"
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define LIBRARY_SEARCH
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end()
#define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS_ )
#define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT
inline void AlertAbort( int n ) { cerr <<
    "abortassert" << endl; }
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : ( a % p ) + p; }
#define POWER( ANSWER , ARGUMENT , EXPONENT ) \
static_assert( ! is_same<TYPE_OF( ARGUMENT ),int>::value && ! is_same<TYPE_OF( ARGUMENT ),uint>::value ); \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
ll ANSWER{ 1 }; \
{ \
ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
#define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_INDEX , CONSTEXPR_LENGTH , MODULO ) \
static ll ANSWER[CONSTEXPR_LENGTH]; \
static ll ANSWER_INV[CONSTEXPR_LENGTH]; \
static ll INVERSE[CONSTEXPR_LENGTH]; \
{ \
ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \
FOREQ( i , 1 , MAX_INDEX ){ \
ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \
} \
ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
FOREQ( i , 2 , MAX_INDEX ){ \
ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = MODULO - ( ( ( MODULO / i ) * INVERSE[MODULO % i] ) % MODULO ) ) %= MODULO
          ; \
} \
} \
//
// EXPRESSIONANSWER調EXPRESSION >= TARGET
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , INEQUALITY , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::value ); \
ll ANSWER = MINIMUM; \
if( MINIMUM <= MAXIMUM ){ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \
while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \
CERR( " " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" <<
          TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH INEQUALITY 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_U = UPDATE_U; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_L = UPDATE_L; \
} \
ANSWER = UPDATE_ANSWER; \
} \
CERR( " " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" <<
        TARGET << ( EXPRESSION > TARGET ? ">0" : EXPRESSION < TARGET ? "<0" : "0" ) ); \
} else { \
CERR( " " << MINIMUM << ">" << MAXIMUM << "" ); \
} \
// 調EXPRESSION >= TARGET
#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , >= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) /
      2 ) \
// 調EXPRESSION <= TARGET
#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , > , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U
      ) / 2 ) \
// 調EXPRESSION >= TARGET
#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , < , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U
      ) / 2 ) \
// 調EXPRESSION <= TARGET
#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET , <= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) /
      2 ) \
//
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
#define ASK_DETAILS( ... ) \
CERR( "" ); \
problems = { __VA_ARGS__ }; \
problems_size = problems.size(); \
FOR( i , 0 , problems_size ){ \
CERR( i << ": " << problems[i] ); \
} \
cin >> num; \
CERR( "" ); \
num_temp = 0; \
if( num < 0 || num >= problems_size ){ \
CERR( "" << problems_size - 1 << "" ); \
CERR( "" ); \
CERR( "" ); \
return -1; \
} \
int LibrarySearch( int num = -1 )
{
vector<string> problems{};
int problems_size = 13;
int num_temp = 0;
string reply{};
if( num == -1 ){
CERR( "[y/n]" );
cin >> reply;
if( reply == "n" ){
CERR( "" );
CERR( "" );
return 0;
} else if( reply != "y" ){
CERR( "y/n" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "" );
ASK_DETAILS(
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
"" ,
""
);
} else {
CERR( "" );
}
CEXPR( int , num_graph , 5 );
CEXPR( int , num_subsequence_sum , 6 );
CEXPR( int , num_game , 8 );
if( num == num_temp++ ){
CERR( "[y/n/c]" );
cin >> reply;
CERR( "" );
if( reply == "y" ){
CERR( "OEIS" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "" );
CERR( "- 調" );
CERR( "- p使" );
CERR( "- pp" );
CERR( " " );
CERR( "" );
} else if( reply == "n" ){
ASK_DETAILS(
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
CERR( "- 調" );
CERR( "- " );
CERR( "- " );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
}
} else {
CERR( "y/n" );
CERR( "" );
CERR( "" );
return -1;
}
CERR( "" );
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
ASK_DETAILS(
"+使" ,
"使" ,
"*使" ,
"*使" ,
"(*,\\cdot)使" ,
"(+,\\cdot)使" ,
"max使"
);
if( num == num_temp++ ){
CERR( "- BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\Tree\\DifferenceSeqeuence" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\IntervalMax\\Template" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- BIT" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template\\Monoid" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Monoid" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SegmentTree" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( " \\Mathematics\\Function\\Encoder" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Dual" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\LazyEvaluation" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "max" );
CERR( "調max調" );
CERR( "" );
CERR( "" );
CERR( "maxmax調" );
CERR( "maxmax" );
CERR( "調" );
CERR( "調" );
CERR( "" );
CERR( "max{0,1}" );
CERR( "使" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "B_qmax(A_i,B_q)" );
CERR( "- A'={(A_i,i)|i}O(N log N)" );
CERR( "- (B_q,q)_qB'O(Q log Q)" );
CERR( "- NC=(0,...,0)O(N)" );
CERR( "B'(B_q,q)" );
CERR( "A'A_i<B_qi" );
CERR( "- A'(A_i,i)O(N)" );
CERR( "- A_i0O(N log N)" );
CERR( "- C_i1O(log N)" );
CERR( "- A+C×B_qO(log N)" );
CERR( "O((N + Q)log N + Q log Q)" );
}
} else if( num == num_temp++ ){
CERR( "fx" );
CERR( "- ixX(i)" );
CERR( "- ixi+1xdX(i)" );
CERR( "" );
CERR( "- O(sum_i X(i) dX(i))fxO(1)ix" );
CERR( "- O(N log_2 X(N))" );
CERR( " - fxO(N)x調x" );
CERR( " - fxO(N/x)x" );
CERR( "- O(N log_2 N)xfxO(log_2 N)" );
CERR( " x" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " " );
CERR( "- " );
CERR( " " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "gcdmax" );
CERR( "" );
} else if( num == num_temp++ ){
return LibrarySearch( num = num_subsequence_sum );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( " - O(N)" );
CERR( " - O(N)" );
CERR( "- " );
CERR( " \\Utility\\String\\RollingHash" );
CERR( "- Z" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N^2)Manacher" );
CERR( " https://snuke.hatenablog.com/entry/2014/12/02/235837" );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- O(N^3)" );
CERR( "- O(N 2^N)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N log_2 N)BIT" );
CERR( " \\Mathematics\\Combinatorial\\Permutation" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "i<j" );
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- 調" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- O(HW)" );
CERR( "- O(HW)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- BFSDijkstra" );
CERR( " \\Utility\\Search\\BreadthFirst" );
CERR( " \\Utility\\Search\\Dijkstra" );
CERR( "- " );
CERR( " - O(V^3)FloydWarshall" );
CERR( " \\Utility\\Search\\FloydWarshall" );
CERR( " - maxO(E(log_2 E + α(V)))UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "HeldKarp" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "\\Utility\\Search\\DepthFirst" );
CERR( "\\Utility\\VLTree" );
} else if( num == num_temp++ ){
CERR( "- 0UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "- " );
CERR( " \\Utility\\Search\\DepthFirst" );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "NWV" );
CERR( "- B=∞" );
CERR( "- B<∞O(2^N)" );
CERR( "- B<∞O(2^{N/2} N)" );
CERR( "- B<∞O(NV)[B-V,B+V]" );
CERR( " " );
CERR( " https://stackoverflow.com/a/18949218" );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
} else if( num == num_temp++ ){
CERR( "NW" );
CERR( "- O(2^N)" );
CERR( "- O(2^N)" );
CERR( "- O(2^{N/2}N)" );
CERR( " " );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
}
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "- " );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace" );
CERR( "- UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "NTK" );
CERR( "- O((N + T)log_2 K)" );
CERR( " \\Mathematics\\Function\\Iteration\\Doubling" );
CERR( "- O(TN)" );
CERR( " \\Mathematics\\Function\\Iteration\\LoopDetection" );
CERR( "- O(N)" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "p" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_game );
}
}
CERR( "" );
CERR( "" );
CERR( "" );
return -1;
}
// intTint
// InitialSegmentSumuintint
// 使
// T& T::operator=( const T& )
// T& T::operator+=( const T& )
// T operator-( const T& , const T& )IntervalSum
// T operator<( const T& , const T& )BinarySearch
template <typename T , int N>
class BIT
{
private:
T m_fenwick[N + 1];
public:
inline BIT();
BIT( const T ( & a )[N] );
// const
inline T Get( const int& i ) const;
inline void Set( const int& i , const T& n );
inline BIT<T,N>& operator+=( const T ( & a )[N] );
void Add( const int& i , const T& n );
T InitialSegmentSum( const int& i_final ) const;
inline T IntervalSum( const int& i_start , const int& i_final ) const;
// operator+=T()
// InitialSegmentSum( i )ni2
int BinarySearch( const T& n ) const;
// IntervalSum( i_start , i )ti_starti2
inline int BinarySearch( const int& i_start , const T& n ) const;
};
template <typename T , int N> inline BIT<T,N>::BIT() : m_fenwick() {}
template <typename T , int N>
BIT<T,N>::BIT( const T ( & a )[N] ) : m_fenwick()
{
for( int j = 1 ; j <= N ; j++ ){
T& fenwick_j = m_fenwick[j];
int i = j - 1;
fenwick_j = a[i];
int i_lim = j - ( j & -j );
while( i != i_lim ){
fenwick_j += m_fenwick[i];
i -= ( i & -i );
}
}
}
template <typename T , int N> inline T BIT<T,N>::Get( const int& i ) const { return IntervalSum( i , i ); }
template <typename T , int N> inline void BIT<T,N>::Set( const int& i , const T& n ) { Add( i , n - IntervalSum( i , i ) ); }
template <typename T , int N> inline BIT<T,N>& BIT<T,N>::operator+=( const T ( & a )[N] ) { for( int i = 0 ; i < N ; i++ ){ Add( i , a[i] ); } return
    *this; }
template <typename T , int N>
void BIT<T,N>::Add( const int& i , const T& n )
{
int j = i + 1;
while( j <= N ){
m_fenwick[j] += n;
j += ( j & -j );
}
return;
}
template <typename T , int N>
T BIT<T,N>::InitialSegmentSum( const int& i_final ) const
{
T sum = 0;
int j = ( i_final < N ? i_final : N - 1 ) + 1;
while( j > 0 ){
sum += m_fenwick[j];
j -= j & -j;
}
return sum;
}
template <typename T , int N> inline T BIT<T,N>::IntervalSum( const int& i_start , const int& i_final ) const { return InitialSegmentSum( i_final ) -
    InitialSegmentSum( i_start - 1 ); }
int main()
{
UNTIE;
LIBRARY_SEARCH;
CEXPR( int , bound_N , 200000 ); // 05
// CEXPR( int , bound_N , 1000000000 ); // 09
// CEXPR( ll , bound_N , 1000000000000000000 ); // 018
CIN_ASSERT( N , 1 , bound_N );
// CEXPR( int , bound_M , 100000 ); // 05
// // CEXPR( int , bound_M , 1000000000 ); // 09
// // CEXPR( ll , bound_M , 1000000000000000000 ); // 018
// CIN_ASSERT( M , 0 , bound_M );
CEXPR( ll , P , 998244353 );
// CEXPR( ll , P , 1000000007 );
static ll power[bound_N];
ll temp = 1;
FOR( i , 0 , N ){
power[i] = temp;
( temp <<= 1 ) < P ? temp : temp -= P;
}
// CEXPR( int , bound_Q , 100000 );
// CIN_ASSERT( Q , 1 , bound_Q );
static pair<int,int> A[bound_N];
FOR( i , 0 , N ){
CIN_ASSERT( Ai , 1 , N );
A[i] = { --Ai , i };
}
sort( A , A + N );
static BIT<int,bound_N> bit0{};
static BIT<ll,bound_N> bit1{};
ll answer = 0;
ll& power_N = power[N-1];
FOREQINV( j , N - 1 , 0 ){
int& i = A[j].second;
bit0.Add( i , 1 );
bit1.Add( i , power[i] );
answer += Residue( bit0.InitialSegmentSum( i - 1 ) * power_N - bit1.InitialSegmentSum( i - 1 ) % P * power[N - 1 - i] , P );
}
// REPEAT( Q ){
// COUT( N );
// }
// CEXPR( int , bound_T , 100000 );
// CIN_ASSERT( T , 1 , bound_T );
// REPEAT( T ){
// COUT( N );
// }
RETURN( Residue( answer , P ) );
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0