-
Notifications
You must be signed in to change notification settings - Fork 27
/
Copy pathDIV3 744 E2.cpp
133 lines (109 loc) · 5.06 KB
/
DIV3 744 E2.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using pbds = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rev(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define bp pop_back
#define mp make_pair
#define all(v) (v).begin() , (v).end()
#define ff first
#define ss second
#define sd(x) ((ll)(v).size())
#define print(x) cout<<x<<"\n"
#define itr(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define PI 3.141592653589793238462
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e13
#define inf 0x3f3f3f3f //1061109567
#define sp(x, y) fixed << setprecision(y) << x << endl;
#define pll pair<ll,ll>
#define zrobits(x) __builtin_ctzll(x)
#define setbits(x) __builtin_popcountll(x)
#define mem(x,y) memset(x, y, sizeof(x))
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; PRINT(x); cerr << endl;
#else
#define debug(x)
#endif
void PRINT(ll t) {cerr << t;}
void PRINT(int t) {cerr << t;}
void PRINT(string t) {cerr << t;}
void PRINT(char t) {cerr << t;}
void PRINT(ld t) {cerr << t;}
void PRINT(double t) {cerr << t;}
void PRINT(ull t) {cerr << t;}
template <class T, class V> void PRINT(pair <T, V> p);
template <class T> void PRINT(vector <T> v);
template <class T> void PRINT(set <T> v);
template <class T, class V> void PRINT(map <T, V> v);
template <class T, class V> void PRINT(unordered_map <T, V> v);
template <class T> void PRINT(multiset <T> v);
template <class T, class V> void PRINT(pair <T, V> p) {cerr << "{"; PRINT(p.ff); cerr << ","; PRINT(p.ss); cerr << "}";}
template <class T> void PRINT(vector <T> v) {cerr << "[ "; for (T i : v) {PRINT(i); cerr << " ";} cerr << "]";}
template <class T> void PRINT(set <T> v) {cerr << "[ "; for (T i : v) {PRINT(i); cerr << " ";} cerr << "]";}
template <class T> void PRINT(multiset <T> v) {cerr << "[ "; for (T i : v) {PRINT(i); cerr << " ";} cerr << "]";}
template <class T, class V> void PRINT(map <T, V> v) {cerr << "[ "; for (auto i : v) {PRINT(i); cerr << " ";} cerr << "]";}
template <class T, class V> void PRINT(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {PRINT(i); cerr << " ";} cerr << "]";}
ll power(ll x, ll y, ll mod) { ll res = 1; x = x % mod; while (y > 0) { if (y & 1) { res = (res * x);} y = y >> 1; x = (x * x); res = res % mod; x = x % mod;} return res % mod;}
ll invert(ll a, ll b) {return power(a, b - 2, b);} //For finding (a^-1)%b which equals to (a^(b-2) )%b(FERMAT'S LITTLE THEOREM)
ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
vector<ll> sieve(ll n) {ll*arr = new ll[n + 1](); vector<ll> vect; for (ll i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (ll j = (ll(i) * ll(i)); j <= n; j += i)arr[j] = 1;} return vect;}
ll next_prime(ll n) {vector<ll>v = sieve(n + 400); auto it = upper_bound(all(v), n); return *it;} // Maximum difference between 2 prime numbers in range of 1 to 1e8 is 220
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, invert(b, m), m) + m) % m;} //If m is prime
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x;}
ll lcm(ll x, ll y) {return (x * y) / gcd(x, y);}
inline long long MAX2(long long a, long long b) {return (a) > (b) ? (a) : (b);}
inline long long MAX3(long long a, long long b, long long c) {return (a) > (b) ? ((a) > (c) ? (a) : (c)) : ((b) > (c) ? (b) : (c));}
inline long long MIN2(long long a, long long b) {return (a) < (b) ? (a) : (b);}
inline long long MIN3(long long a, long long b, long long c) {return (a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c));}
// ll *fact = new ll[200000 + 5];
// ll *ifact = new ll[200000 + 5];
void solution()
{
pbds <ll>p;
deque<ll>dq;
ll n, x, ind1, ind2, cnt = 0;
cin >> n;
map<ll, ll>m1;
f(i, 0, n) {
cin >> x;
ind1 = p.order_of_key(x);
ind2 = ind1 + m1[x];
m1[x]++;
cnt += min(ind1, i - ind2);
p.insert(x);
}
print(cnt);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("check.txt", "w", stderr);
#endif
FAST_IO;
// // FOR FINDING FACTORIAL OF NUMBERS FROM 1 TO 2*10^5 and here MODULO is 1e9+7
// fact[0] = 1, ifact[0] = 1;
// for (ll i = 1; i <= 2e5; i++) {
// fact[i] = mod_mul(fact[i - 1], i, MOD);
// ifact[i] = invert(fact[i], MOD);
// }
ll t = 1;
cin >> t;
f(i, 0, t)
{
solution();
}
}