#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Xorshift { private: uint32_t x, y, z, w; public: Xorshift(uint32_t seed=88675123, int32_t loop=50){ x = 123456789; y = 362436069; z = 521288629; w = seed; while(--loop >= 0){ (*this)(); } } uint32_t operator()(){ uint32_t t=(x^(x<<11)); x=y; y=z; z=w; return w=(w^(w>>19))^(t^(t>>8)); } uint32_t operator()(uint32_t size){ return (*this)() % size; } }; Xorshift xorshift; int quickSelect(vector::iterator left, vector::iterator right, int index) { int n = right - left; if(n == 1) return *left; swap(*left, *(left + xorshift(n))); auto it1 = left + 1; auto it2 = right - 1; int k = 0; while(it1 <= it2){ if(*it1 < *left || (*it1 == *left && (k++) % 2 == 0)){ ++ it1; } else{ swap(*it1, *it2); -- it2; } } swap(*left, *it2); int m = it2 - left; if(index < m) return quickSelect(left, it2, index); else if(index == m) return *it2; else return quickSelect(it1, right, index - m - 1); } int main() { int n; cin >> n; vector a(n); for(int i=0; i> a[i]; long long ans = 0; for(int len=1; len<=n; ++len){ cerr << len << endl; int m = n / len; vector a1 = a; vector a2 = a; vector v1(m+1), v2(m+1); for(int i=0; i