QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725590#7956. Walk Swappinggugugaga#AC ✓361ms3952kbC++2010.6kb2024-11-08 18:56:512024-11-08 18:56:51

Judging History

你现在查看的是最新测评结果

  • [2024-11-08 18:56:51]
  • 评测
  • 测评结果:AC
  • 用时:361ms
  • 内存:3952kb
  • [2024-11-08 18:56:51]
  • 提交

answer

/*************************************
*    author: marvinthang             *
*    created: 08.11.2024 16:58:28    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define             fi  first
#define             se  second
#define           left  ___left___
#define          right  ___right___
#define   scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define  print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
	#include "debug.h"
#else
	#define DB(...)
	#define db(...) ""
	#define debug(...)
#endif

namespace std {
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream &print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))>typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class T> print_op(stack <T>) { vector <T> v; stack <T> st = u; while (!st.empty()) v.push_back(st.top()), st.pop(); reverse(v.begin(), v.end()); return out << v; }
template <class T> print_op(queue <T>) { queue <T> q = u; out << '{'; while (!q.empty()) { out << q.front(); q.pop(); if (!q.empty()) out << ", "; } out << '}'; return out; }
template <class T, class X, class Y> print_op(priority_queue <T, X, Y>) { priority_queue <T, X, Y> pq = u; out << '{'; while (!pq.empty()) { out << pq.top(); pq.pop(); if (!pq.empty()) out << ", "; } out << '}'; return out; }
template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)) {} template <class...Args> decltype(auto)operator()(Args &&...args) { return fun_(ref(*this), forward<Args>(args)...); } };
template <class Fun> decltype(auto)y_combinator(Fun &&fun) { return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun)); }
template <typename T, int D> struct Vec: public vector <Vec<T, D - 1>> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template <typename ...Args> Vec(int n = 0, Args ...args): vector <Vec<T, D - 1>>(n, Vec<T, D - 1>(args...)) {} };
template <typename T> struct Vec<T, 1>: public vector<T>{ Vec(int n = 0, const T &val = T()): vector<T>(n, val) {} };
#if __cplusplus < 202002L
	template <class T> int ssize(const T &a) { return a.size(); }
#endif
}

namespace MODINT {
struct barrett {
	unsigned int _m;
	unsigned long long im;
	explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
	unsigned int umod() const { return _m; };
	unsigned int mul(unsigned int a, unsigned int b) const {
		unsigned long long z = a; z *= b;
		unsigned long long x = (unsigned long long)(((unsigned __int128) z * im) >> 64);
		unsigned long long y = x * _m;
		return (unsigned int)(z - y + (z < y ? _m : 0));
	}
};
template <class T> T invGeneral(T a, T b) {
	a %= b;
	if (!a) return b == 1 ? 0 : -1;
	T x = invGeneral(b, a);
	return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
}
template <int m, enable_if_t<1 <= m>* = nullptr>
struct static_modint {
using mint = static_modint;
public:
	static constexpr int mod() { return m; }
	static mint raw(int v) {
		mint x; x.v = v;
		return x;
	}
	static_modint(): v(0) {}
	template <class T> static_modint(T x) {
		int y;
		if (x < 0) {
			if (x < -mod()) y = x % mod();
			else y = x;
			if (y < 0) y += mod();
		} else {
			if (x < mod()) y = x;
			else y = x % mod();
		}
		v = y;
	}
	unsigned int val() const { return v; }
	unsigned int operator () () const { return v; }
	mint & operator ++ () { if (++v == umod()) v = 0; return *this; }
	mint & operator -- () { if (!v) v = umod(); --v; return *this; }
	mint operator ++ (int) { mint old = *this; ++*this; return old; }
	mint operator -- (int) { mint old = *this; --*this; return old; }
	mint operator + () { return *this; }
	mint operator - () { return raw(!v ? 0 : umod() - v); }
	mint & operator += (const mint &rhs) { v += rhs.v; if (v >= umod()) v -= umod(); return *this; }
	mint & operator -= (const mint &rhs) { v -= rhs.v; if (v >= umod()) v += umod(); return *this; }
	mint & operator *= (const mint &rhs) {
		unsigned long long z = v; z *= rhs.v; v = z % umod();
		return *this;
	}
	mint & operator /= (const mint &rhs) { return *this *= rhs.inv(); }
	friend mint operator + (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
	friend mint operator - (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
	friend mint operator * (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
	friend mint operator / (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
	mint pow(long long n) const {
		assert(0 <= n);
		mint res = 1, a = *this;
		for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
		return res;
	}
	mint inv() const {
		int i = invGeneral((int) v, mod());
		assert(~i);
		return i;
	}
	friend bool operator == (const mint& lhs, const mint& rhs) { return lhs.v == rhs.v; }
	friend bool operator != (const mint& lhs, const mint& rhs) { return lhs.v != rhs.v; }
	friend ostream & operator << (ostream &out, const mint &x) { return out << x.v; }
	friend istream & operator >> (istream &in, mint &x) { long long a; in >> a; x = a; return in; }
	explicit operator bool() const { return v; }
	explicit operator int() const { return v; }
private:
	unsigned int v;
	static constexpr unsigned int umod() { return m; }
};
template <int id> struct dynamic_modint {
using mint = dynamic_modint;
public:
	static int mod() { return (int) bt.umod(); }
	static void set_mod(int m) {
		assert(1 <= m);
		bt = barrett(m);
	}
	static mint raw(int v) {
		mint x; x.v = v;
		return x;
	}
	dynamic_modint(): v(0) {}
	template <class T> dynamic_modint(T x) {
		int y;
		if (x < 0) {
			if (x < -mod()) y = x % mod();
			else y = x;
			if (y < 0) y += mod();
		} else {
			if (x < mod()) y = x;
			else y = x % mod();
		}
		v = y;
	}
	unsigned int val() const { return v; }
	unsigned int operator () () const { return v; }
	mint & operator ++ () { if (++v == umod()) v = 0; return *this; }
	mint & operator -- () { if (!v) v = umod(); --v; return *this; }
	mint operator ++ (int) { mint old = *this; ++*this; return old; }
	mint operator -- (int) { mint old = *this; --*this; return old; }
	mint operator + () { return *this; }
	mint operator - () { return raw(!v ? 0 : umod() - v); }
	mint & operator += (const mint &rhs) { v += rhs.v; if (v >= umod()) v -= umod(); return *this; }
	mint & operator -= (const mint &rhs) { v -= rhs.v; if (v >= umod()) v += umod(); return *this; }
	mint & operator *= (const mint &rhs) {
		v = bt.mul(v, rhs.v);
		return *this;
	}
	mint & operator /= (const mint &rhs) { return *this *= rhs.inv(); }
	friend mint operator + (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
	friend mint operator - (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
	friend mint operator * (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
	friend mint operator / (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
	mint pow(long long n) const {
		assert(0 <= n);
		mint res = 1, a = *this;
		for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
		return res;
	}
	mint inv() const {
		int i = invGeneral((int) v, mod());
		assert(~i);
		return i;
	}
	friend bool operator == (const mint& lhs, const mint& rhs) { return lhs.v == rhs.v; }
	friend bool operator != (const mint& lhs, const mint& rhs) { return lhs.v != rhs.v; }
	friend ostream & operator << (ostream &out, const mint &x) { return out << x.v; }
	friend istream & operator >> (istream &in, mint &x) { long long a; in >> a; x = a; return in; }
	explicit operator bool() const { return v; }
	explicit operator int() const { return v; }
private:
	unsigned int v;
	static barrett bt;
	static unsigned int umod() { return bt.umod(); }
};
template <int id> barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint <-1>;
using Modular = modint1000000007;
} using namespace MODINT;

const int base = 311;

long long inf = 1e18;
void process(void) {
	int n; cin >> n;
	vector <int> a(n), b(n); cin >> a >> b;
	long long res = inf;
	vector <Modular> pw(n + n + 1);
	pw[0] = 1;
	for (int i = 1; i <= n + n; ++i) pw[i] = pw[i - 1] * base;
	for (int f = 0; f < n; ++f) {
		long long cur = inf;
		for (int t = 0; t < 2; ++t) {
			vector <int> pos;
			for (int i = 0; i < n; ++i) if (a[i] != b[i]) pos.push_back(i);
			vector <Modular> ha(n + n + 1), hb(n + n + 1);
			for (int i = 0; i < n + n; ++i) {
				ha[i + 1] = ha[i] * base + a[i < n ? i : i - n];
				hb[i + 1] = hb[i] * base + b[i < n ? i : i - n];
			}
			auto get_hash_b = [&] (int l, int r) {
				++l; ++r;
				if (r < l) r += n;
				return hb[r] - hb[l - 1] * pw[r - l + 1];
			};
			auto get_hash_a = [&] (int l, int r) {
				++l; ++r;
				if (r < l) r += n;
				return ha[r] - ha[l - 1] * pw[r - l + 1];
			};
			auto get_hash_a_shift = [&] (int l, int r) -> Modular {
				int p = a[l < n ? l : l - n];
				if (l == r) return p;
				if (r < l) r += n;
				return get_hash_a(l + 1, r) * base + p;
			};
			if (pos.empty()) cur = 0;
			else if (ssize(pos) > 1) {
				auto check = [&] (int l, int r) {
					return get_hash_b(l, r) == get_hash_a_shift(l, r);
				};
				for (int i = 0; i < ssize(pos); ++i) {
					int l = pos[i], r = !i ? pos.back() : pos[i - 1];
					if (check(l, r)) cur = min<long long>(cur, r - l + (r - l < 0 ? n : 0));
				}
			}
			reverse(a.begin(), a.end());
			reverse(b.begin(), b.end());
		}
		res = min(res, 1LL * (n - 1) * min(f, n - f) + cur);
		rotate(a.begin(), a.begin() + 1, a.end());
	}
	cout << (res == inf ? -1 : res) << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	file("test");
	// int t; cin >> t; while (t--)
	process();
	return (0^0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3504kb

input:

4
4 3 2 1
3 4 2 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

6
2 1 1 2 2 1
1 2 2 2 1 1

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

6
4 1 3 6 2 5
6 2 1 3 4 5

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4
1 2 3 4
4 2 1 3

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

6
4 1 3 6 2 5
6 2 5 3 4 1

output:

13

result:

ok single line: '13'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

6
4 1 3 3 2 5
3 2 5 3 4 1

output:

12

result:

ok single line: '12'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

5
4 3 5 2 1
1 3 5 4 2

output:

2

result:

ok single line: '2'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

5
4 3 5 2 1
1 4 3 5 2

output:

4

result:

ok single line: '4'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

5
1 1 1 2 1
2 1 1 1 1

output:

2

result:

ok single line: '2'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

4
4 3 2 1
1 3 2 4

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

4
4 3 2 1
1 3 4 2

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

10
2 3 1 1 3 4 5 5 6 1
1 1 3 4 5 3 5 1 7 2

output:

-1

result:

ok single line: '-1'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

5
1 4 5 3 2
5 3 2 1 4

output:

8

result:

ok single line: '8'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

5
1 2 3 4 5
5 2 1 3 4

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

10
1 2 3 4 5 6 7 8 9 10
8 4 2 3 1 5 7 6 9 10

output:

-1

result:

ok single line: '-1'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

10
1 2 3 2 2 2 1 1 1 1
2 1 1 1 1 1 2 2 3 2

output:

41

result:

ok single line: '41'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

10
1 1 1 2 2 4 4 4 2 2
1 1 2 2 4 4 2 2 1 4

output:

12

result:

ok single line: '12'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

12
3 3 3 2 2 2 4 4 2 2 1 3
3 3 2 2 4 4 2 2 2 1 3 3

output:

13

result:

ok single line: '13'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

12
3 3 2 2 2 2 4 4 2 2 1 2
2 2 2 2 4 4 2 2 2 1 3 3

output:

19

result:

ok single line: '19'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

12
3 3 2 4 2 2 4 4 2 2 1 2
2 2 2 2 4 4 2 2 4 1 3 3

output:

-1

result:

ok single line: '-1'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

20
3 4 4 5 1 2 3 2 5 1 1 5 3 2 4 5 1 2 3 5
2 3 5 4 4 5 1 2 3 2 5 3 1 1 5 3 2 4 5 1

output:

49

result:

ok single line: '49'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

20
3 4 4 5 1 2 3 2 5 1 1 5 3 2 4 5 1 2 3 5
3 2 3 4 5 1 2 3 5 4 4 5 1 2 3 2 5 1 1 5

output:

158

result:

ok single line: '158'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

100
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
99 1...

output:

109

result:

ok single line: '109'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

100
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
100 ...

output:

89

result:

ok single line: '89'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

100
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
51 5...

output:

4924

result:

ok single line: '4924'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

100
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
51 5...

output:

4905

result:

ok single line: '4905'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

100
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20
9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 1...

output:

3990

result:

ok single line: '3990'

Test #29:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ...

output:

125

result:

ok single line: '125'

Test #30:

score: 0
Accepted
time: 1ms
memory: 3508kb

input:

100
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20
9 9 9 9 9 10 10 10 10 10 11 11 11 15 11 1...

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ...

output:

79

result:

ok single line: '79'

Test #32:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ...

output:

-1

result:

ok single line: '-1'

Test #33:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

100
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...

output:

0

result:

ok single line: '0'

Test #34:

score: 0
Accepted
time: 39ms
memory: 3608kb

input:

1000
458 51 4 190 103 444 401 456 34 970 169 517 283 66 571 282 233 161 32 376 168 616 993 347 213 597 334 652 471 532 552 987 353 613 665 305 477 632 331 293 939 598 175 813 10 890 423 560 502 857 277 18 283 461 6 231 233 648 929 75 896 807 900 2 582 84 81 107 255 145 909 562 492 58 218 575 7 610 6...

output:

243210

result:

ok single line: '243210'

Test #35:

score: 0
Accepted
time: 39ms
memory: 3604kb

input:

1000
323 302 194 991 814 729 763 611 294 128 752 772 136 693 300 575 118 965 888 999 288 837 534 470 436 195 8 958 448 216 697 295 53 341 577 460 543 724 79 593 490 800 218 336 7 448 401 716 7 920 740 21 87 208 202 422 812 528 196 475 633 732 170 423 975 901 412 117 829 457 420 941 664 644 858 473 9...

output:

243013

result:

ok single line: '243013'

Test #36:

score: 0
Accepted
time: 360ms
memory: 3632kb

input:

3000
2057 2074 2349 1090 597 671 2074 92 892 304 1749 2393 935 2200 2859 293 2392 127 1960 1991 1842 2447 1783 1669 599 1936 887 1490 296 478 2334 250 864 1697 1833 325 1801 2950 2704 51 1868 2860 820 1495 1123 1 2122 2135 1826 294 612 1771 2181 160 1358 587 931 409 934 2622 516 2199 399 1008 1446 3...

output:

1788777

result:

ok single line: '1788777'

Test #37:

score: 0
Accepted
time: 351ms
memory: 3684kb

input:

3000
324 151 600 776 956 914 289 189 861 149 898 483 603 415 202 265 317 689 383 59 610 507 832 589 689 135 67 296 941 795 53 539 385 469 824 742 232 843 890 363 768 144 132 991 472 142 671 655 327 648 310 46 47 654 344 326 91 79 852 109 620 514 43 114 538 374 160 296 897 755 995 514 746 304 830 455...

output:

1100867

result:

ok single line: '1100867'

Test #38:

score: 0
Accepted
time: 357ms
memory: 3952kb

input:

3000
1991 2302 2034 674 671 2189 1348 2644 189 991 1293 60 489 514 1203 1906 2376 2579 482 2083 2116 2055 278 1787 445 1557 1583 373 1959 523 322 2449 1643 1654 734 24 1211 1758 2876 261 1936 2105 1482 2069 1894 974 673 392 1739 1181 758 576 1004 2645 1782 2817 152 2654 2694 2553 1897 2937 130 1178 ...

output:

742350

result:

ok single line: '742350'

Test #39:

score: 0
Accepted
time: 353ms
memory: 3752kb

input:

3000
527 569 638 129 325 581 270 91 113 516 804 284 17 367 470 304 847 659 40 504 483 25 109 300 268 189 9 409 405 337 957 468 573 515 115 429 905 252 170 134 998 786 564 742 410 512 598 641 234 884 231 859 530 170 349 653 704 439 381 215 505 337 521 423 88 941 951 17 892 960 263 991 642 482 5 418 8...

output:

1930377

result:

ok single line: '1930377'

Test #40:

score: 0
Accepted
time: 357ms
memory: 3748kb

input:

3000
3 72 35 97 25 59 36 93 74 34 78 47 60 99 94 62 82 66 81 66 79 50 18 24 83 39 97 27 17 69 43 40 88 84 34 73 33 60 46 61 88 59 85 79 43 1 27 8 39 11 24 53 72 47 66 78 15 79 89 84 54 84 94 21 12 44 48 1 5 27 13 67 64 27 92 86 80 90 21 61 40 57 70 50 34 86 84 86 9 25 38 75 81 82 1 50 72 25 15 15 7 ...

output:

1072255

result:

ok single line: '1072255'

Test #41:

score: 0
Accepted
time: 356ms
memory: 3912kb

input:

3000
8 8 7 4 4 3 2 4 3 2 8 7 10 7 2 3 8 6 4 2 1 4 1 3 1 4 2 4 4 1 8 9 4 9 4 6 9 3 4 3 6 5 5 10 7 10 7 3 5 7 2 8 9 8 9 7 6 7 1 9 6 6 10 4 2 7 8 9 7 2 10 4 3 7 4 9 4 9 10 3 5 10 1 3 7 6 1 10 4 9 4 7 6 4 2 8 1 5 6 9 4 10 8 1 5 10 7 9 7 3 6 1 2 7 4 1 3 7 9 10 3 3 6 10 6 4 1 7 3 9 3 9 4 6 3 5 2 8 5 1 2 2...

output:

3327362

result:

ok single line: '3327362'

Test #42:

score: 0
Accepted
time: 361ms
memory: 3788kb

input:

3000
9 4 1 8 8 8 6 10 8 3 10 4 2 8 10 4 9 3 10 4 1 8 6 3 3 4 3 5 4 1 9 2 6 5 3 5 6 5 2 10 1 10 6 9 9 3 5 9 2 4 9 1 9 4 7 4 1 4 5 1 4 3 10 3 10 9 7 7 7 8 3 3 10 10 5 2 5 9 3 2 4 9 3 1 7 6 6 10 7 5 4 9 8 9 3 10 6 5 6 7 7 3 4 7 3 3 1 6 2 7 4 1 6 10 4 9 5 5 9 1 1 2 1 10 4 4 5 6 6 3 9 3 8 5 10 6 2 2 7 5 ...

output:

3923978

result:

ok single line: '3923978'

Test #43:

score: 0
Accepted
time: 357ms
memory: 3684kb

input:

3000
819 372 497 415 334 981 419 328 220 437 701 858 694 874 527 446 983 554 660 400 833 912 537 245 255 260 277 861 260 526 841 349 682 12 722 193 404 701 341 416 512 156 130 712 551 264 724 532 888 227 1000 579 92 514 612 851 66 509 546 829 110 696 564 875 366 825 522 975 134 891 579 518 420 58 84...

output:

-1

result:

ok single line: '-1'

Test #44:

score: 0
Accepted
time: 359ms
memory: 3720kb

input:

3000
39 51 14 2 62 32 10 73 21 14 44 5 27 44 54 95 67 69 98 69 48 29 55 86 62 13 49 43 91 75 82 9 58 64 45 48 74 77 3 66 54 28 57 72 67 72 81 8 3 82 8 64 21 78 67 42 77 73 49 29 62 59 60 70 36 80 19 66 3 95 56 19 85 11 38 29 11 34 69 71 31 27 93 31 96 47 71 90 2 93 57 15 44 14 37 70 28 95 77 92 33 3...

output:

-1

result:

ok single line: '-1'

Test #45:

score: 0
Accepted
time: 360ms
memory: 3668kb

input:

3000
2 1 2 1 2 2 2 2 1 2 1 2 2 2 2 2 2 1 2 1 2 2 1 2 1 1 1 2 1 2 2 2 2 2 1 2 2 1 1 1 2 2 1 1 1 2 2 2 2 1 2 2 2 2 2 1 1 1 2 1 2 1 2 1 1 1 2 2 1 2 2 2 2 2 2 1 2 1 1 1 2 1 2 1 1 1 2 1 1 2 1 2 1 1 1 1 2 1 2 1 1 2 1 2 1 1 1 2 1 2 1 1 2 2 2 2 1 2 2 1 1 1 2 2 1 2 1 2 1 2 1 2 1 2 2 2 1 2 2 1 1 2 2 2 2 1 2 2...

output:

-1

result:

ok single line: '-1'

Test #46:

score: 0
Accepted
time: 360ms
memory: 3736kb

input:

3000
1 2 2 1 2 1 2 2 2 1 2 1 1 2 2 1 2 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 1 1 2 1 2 1 1 1 1 1 1 2 1 2 2 1 1 1 1 2 1 2 2 1 1 2 1 2 2 1 2 2 2 2 1 1 2 1 1 1 1 2 2 1 2 1 1 2 2 2 1 2 2 2 1 1 2 2 1 1 2 2 2 1 2 2 1 2 2 1 2 2 2 1 1 2 1 1 2 2 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 2 2 2 2 1 1 2 2 1 2 2 1 1 1 1 2 2 1...

output:

-1

result:

ok single line: '-1'

Test #47:

score: 0
Accepted
time: 360ms
memory: 3672kb

input:

3000
2 2 2 1 2 1 2 1 2 2 2 2 1 1 1 1 2 2 2 1 1 2 1 1 2 1 1 2 2 1 2 1 1 2 1 2 2 2 1 2 1 2 2 1 1 1 2 2 2 2 2 1 1 2 2 1 1 2 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 1 1 1 2 1 2 2 2 2 1 2 1 1 2 2 2 2 1 2 2 1 2 1 1 1 1 2 1 2 1 1 2 1 2 2 2 2 1 1 1 2 1 1 2 2 2 2 1 2 2 1 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1 1 1 1 1 2 1 1 1...

output:

-1

result:

ok single line: '-1'

Test #48:

score: 0
Accepted
time: 356ms
memory: 3668kb

input:

3000
1 3000 3000 1 3000 1 1 3000 3000 1 1 1 3000 1 1 3000 3000 1 1 3000 3000 3000 3000 1 1 1 3000 1 1 3000 3000 1 1 1 1 3000 1 3000 3000 1 3000 1 3000 1 1 3000 3000 1 1 1 1 1 3000 1 1 1 1 1 1 3000 1 1 3000 1 1 3000 1 3000 1 3000 3000 3000 3000 1 3000 1 1 1 3000 1 3000 1 3000 3000 3000 3000 1 1 1 1 3...

output:

1221180

result:

ok single line: '1221180'

Test #49:

score: 0
Accepted
time: 361ms
memory: 3664kb

input:

3000
1 3000 1 1 3000 3000 3000 3000 3000 1 1 1 3000 1 1 3000 3000 3000 3000 1 3000 3000 3000 1 1 3000 1 3000 1 1 3000 1 3000 3000 3000 3000 1 1 3000 3000 1 3000 1 3000 3000 1 1 3000 1 3000 1 3000 1 3000 3000 1 3000 3000 1 1 1 1 1 3000 3000 1 1 3000 1 1 1 1 1 3000 3000 1 1 1 1 3000 1 3000 3000 3000 3...

output:

3646897

result:

ok single line: '3646897'

Test #50:

score: 0
Accepted
time: 360ms
memory: 3740kb

input:

3000
1 3000 3000 3000 3000 1 3000 3000 1 1 1 1 3000 3000 3000 3000 3000 1 1 1 3000 1 1 1 1 3000 1 1 1 3000 1 3000 1 3000 3000 1 1 1 1 3000 1 3000 3000 3000 3000 1 3000 1 1 1 3000 3000 1 1 1 3000 3000 3000 1 3000 3000 3000 1 3000 1 1 1 1 1 1 1 1 3000 1 3000 1 1 3000 1 1 1 1 3000 3000 3000 1 1 1 3000 ...

output:

3890174

result:

ok single line: '3890174'

Test #51:

score: 0
Accepted
time: 360ms
memory: 3672kb

input:

3000
1 1 3000 3000 3000 3000 3000 1 3000 3000 3000 1 3000 3000 3000 1 1 3000 1 1 1 1 3000 1 3000 3000 1 1 1 3000 3000 3000 3000 1 1 3000 1 1 1 1 1 3000 3000 1 3000 1 3000 1 1 3000 1 1 1 3000 1 3000 1 3000 3000 3000 3000 3000 1 1 1 3000 3000 3000 1 3000 1 1 3000 3000 1 1 3000 3000 3000 3000 3000 1 30...

output:

2288229

result:

ok single line: '2288229'

Test #52:

score: 0
Accepted
time: 353ms
memory: 3672kb

input:

3000
3000 1 1 3000 3000 3000 1 3000 1 3000 1 1 3000 3000 1 1 3000 1 1 1 1 3000 3000 3000 3000 1 1 1 3000 3000 3000 3000 3000 3000 1 3000 1 3000 3000 1 3000 1 1 3000 3000 3000 3000 3000 1 3000 3000 3000 1 3000 3000 3000 3000 3000 1 1 3000 3000 1 3000 3000 1 3000 3000 3000 1 3000 3000 3000 1 1 3000 1 ...

output:

1856371

result:

ok single line: '1856371'

Test #53:

score: 0
Accepted
time: 360ms
memory: 3900kb

input:

3000
3000 3000 1 1 3000 3000 3000 3000 1 3000 3000 1 3000 1 1 1 1 3000 3000 3000 3000 3000 1 1 3000 1 3000 1 1 1 1 1 1 3000 3000 1 3000 1 1 3000 1 3000 1 1 3000 1 3000 3000 1 3000 1 3000 3000 1 3000 3000 3000 1 3000 3000 3000 3000 1 1 3000 1 3000 3000 3000 3000 3000 3000 3000 1 1 3000 1 1 3000 3000 ...

output:

2756080

result:

ok single line: '2756080'