void solve( std:: istream & in, std:: ostream & out) {
int n;
in >> n;
using Z = ZnConst< 1000000007 > ;
int mx = 2500001 ;
vector< int > v( n) ;
struct Info {
int pos, ans;
Z c;
} ;
vector< vector< Info>> infos( mx) ;
//for (int i: range(mx)) { //initialize lazily
// infos[i].push_back({-1, 0, Z::rawValueOf(1)});
//}
struct PrefInfo {
Z sum, sumcpos;
} ;
vector< vector< PrefInfo>> prefs( mx) ;
//for (int i: range(mx)) {
// prefs[i].push_back({Z(), Z()});
// prefs[i].push_back({Z::rawValueOf(1), Z::valueOf(-1)});
//}
vector< pair< int , int >> gcds;
for ( int i: range( n) ) {
in >> v[ i] ;
}
gcds.push_back ( { - 1 , - 1 } ) ;
for ( int i: range( n) ) {
vector< pair< int , int >> newgcd;
newgcd.push_back ( { - 1 , - 1 } ) ;
for ( auto j = 1 ; j < gcds.size ( ) ; ++ j) {
auto g = gcds[ j] ;
g.first = gcd( g.first , v[ i] ) ;
if ( g.first == newgcd.back ( ) .first ) {
newgcd.back ( ) .second = g.second ;
} else {
newgcd.emplace_back ( g.first , g.second ) ;
}
}
newgcd.emplace_back ( v[ i] , i) ;
gcds = move( newgcd) ;
for ( int j = 1 ; j < gcds.size ( ) ; ++ j) {
int g = gcds[ j] .first ;
if ( infos[ g] .empty ( ) ) { // fixing mempry problems
infos[ g] .push_back ( { - 1 , 0 , Z:: rawValueOf ( 1 ) } ) ;
prefs[ g] .push_back ( { Z( ) , Z( ) } ) ;
prefs[ g] .push_back ( { Z:: rawValueOf ( 1 ) , Z:: valueOf ( - 1 ) } ) ;
}
auto endofgood = std:: partition_point ( infos[ g] .begin ( ) , infos[ g] .end ( ) , [ & ] ( Info info) {
return info.pos < gcds[ j] .second ;
} ) - infos[ g] .begin ( ) ;
Info new_info = { i, - 1 , Z:: valueOf ( 0 ) } ;
new_info.ans = infos[ g] [ endofgood - 1 ] .ans + 1 ;
auto start_of_same_answer = std:: partition_point ( infos[ g] .begin ( ) , infos[ g] .end ( ) , [ & ] ( Info info) {
return info.ans < new_info.ans - 1 ;
} ) - infos[ g] .begin ( ) ;
auto center = std:: partition_point ( infos[ g] .begin ( ) , infos[ g] .end ( ) , [ & ] ( Info info) {
return info.pos < gcds[ j - 1 ] .second ;
} ) - infos[ g] .begin ( ) ;
if ( center >= start_of_same_answer) {
new_info.c + = ( prefs[ g] [ center] .sum - prefs[ g] [ start_of_same_answer] .sum ) * ( gcds[ j] .second - gcds[ j - 1 ] .second ) ;
}
int st = ( int ) max( center, start_of_same_answer) ;
new_info.c + = gcds[ j] .second * ( prefs[ g] [ endofgood] .sum - prefs[ g] [ st] .sum ) - ( prefs[ g] [ endofgood] .sumcpos - prefs[ g] [ st] .sumcpos ) ;
infos[ g] .push_back ( new_info) ;
prefs[ g] .push_back ( { prefs[ g] .back ( ) .sum + new_info.c , prefs[ g] .back ( ) .sumcpos + new_info.c * new_info.pos } ) ;
}
}
int maxans = 0 ;
for ( int i: range( mx) ) {
if ( ! infos[ i] .empty ( ) ) {
maxans = max( maxans, infos[ i] .back ( ) .ans ) ;
}
}
Z res;
for ( int i: range( mx) ) {
for ( auto t: infos[ i] ) {
if ( t.ans == maxans) {
res + = t.c ;
}
}
}
out << maxans << ' ' << res << "\n " ;
}
dm9pZCBzb2x2ZShzdGQ6OmlzdHJlYW0mIGluLCBzdGQ6Om9zdHJlYW0mIG91dCkgewoJCWludCBuOwoJCWluID4+IG47CgkJdXNpbmcgWiA9IFpuQ29uc3Q8MTAwMDAwMDAwNz47CgkJaW50IG14ID0gMjUwMDAwMTsKCQl2ZWN0b3I8aW50PiB2KG4pOwoJCXN0cnVjdCBJbmZvIHsKCQkJaW50IHBvcywgYW5zOwoJCQlaIGM7CgkJfTsKCQl2ZWN0b3I8dmVjdG9yPEluZm8+PiBpbmZvcyhteCk7CgkJLy9mb3IgKGludCBpOiByYW5nZShteCkpIHsgLy9pbml0aWFsaXplIGxhemlseQoJCS8vCWluZm9zW2ldLnB1c2hfYmFjayh7LTEsIDAsIFo6OnJhd1ZhbHVlT2YoMSl9KTsKCQkvL30KCQlzdHJ1Y3QgUHJlZkluZm8gewoJCQlaIHN1bSwgc3VtY3BvczsKCQl9OwoJCXZlY3Rvcjx2ZWN0b3I8UHJlZkluZm8+PiBwcmVmcyhteCk7CgkJLy9mb3IgKGludCBpOiByYW5nZShteCkpIHsKCQkvLwlwcmVmc1tpXS5wdXNoX2JhY2soe1ooKSwgWigpfSk7CgkJLy8JcHJlZnNbaV0ucHVzaF9iYWNrKHtaOjpyYXdWYWx1ZU9mKDEpLCBaOjp2YWx1ZU9mKC0xKX0pOwoJCS8vfQoKCQl2ZWN0b3I8cGFpcjxpbnQsIGludD4+IGdjZHM7CgkJZm9yIChpbnQgaTogcmFuZ2UobikpIHsKCQkJaW4gPj4gdltpXTsKCQl9CgoJCWdjZHMucHVzaF9iYWNrKHstMSwgLTF9KTsKCgkJZm9yIChpbnQgaTogcmFuZ2UobikpIHsKCQkJdmVjdG9yPHBhaXI8aW50LCBpbnQ+PiBuZXdnY2Q7CgkJCW5ld2djZC5wdXNoX2JhY2soey0xLCAtMX0pOwoJCQlmb3IgKGF1dG8gaiA9IDE7IGogPCBnY2RzLnNpemUoKTsgKytqKSB7CgkJCQlhdXRvIGcgPSBnY2RzW2pdOwoJCQkJZy5maXJzdCA9IGdjZChnLmZpcnN0LCB2W2ldKTsKCQkJCWlmIChnLmZpcnN0ID09IG5ld2djZC5iYWNrKCkuZmlyc3QpIHsKCQkJCQluZXdnY2QuYmFjaygpLnNlY29uZCA9IGcuc2Vjb25kOwoJCQkJfSBlbHNlIHsKCQkJCQluZXdnY2QuZW1wbGFjZV9iYWNrKGcuZmlyc3QsIGcuc2Vjb25kKTsKCQkJCX0KCQkJfQoJCQluZXdnY2QuZW1wbGFjZV9iYWNrKHZbaV0sIGkpOwoKCQkJZ2NkcyA9IG1vdmUobmV3Z2NkKTsKCgkJCWZvciAoaW50IGogPSAxOyBqIDwgZ2Nkcy5zaXplKCk7ICsraikgewoJCQkJaW50IGcgPSBnY2RzW2pdLmZpcnN0OwoJCQkJaWYgKGluZm9zW2ddLmVtcHR5KCkpIHsgLy8gZml4aW5nIG1lbXByeSBwcm9ibGVtcwoJCQkJCWluZm9zW2ddLnB1c2hfYmFjayh7LTEsIDAsIFo6OnJhd1ZhbHVlT2YoMSl9KTsKCQkJCQlwcmVmc1tnXS5wdXNoX2JhY2soe1ooKSwgWigpfSk7CgkJCQkJcHJlZnNbZ10ucHVzaF9iYWNrKHtaOjpyYXdWYWx1ZU9mKDEpLCBaOjp2YWx1ZU9mKC0xKX0pOwoJCQkJfQoJCQkJYXV0byBlbmRvZmdvb2QgPSBzdGQ6OnBhcnRpdGlvbl9wb2ludChpbmZvc1tnXS5iZWdpbigpLCBpbmZvc1tnXS5lbmQoKSwgWyZdKEluZm8gaW5mbykgewoJCQkJCXJldHVybiBpbmZvLnBvcyA8IGdjZHNbal0uc2Vjb25kOwoJCQkJfSkgLSBpbmZvc1tnXS5iZWdpbigpOwoKCQkJCUluZm8gbmV3X2luZm8gPSB7aSwgLTEsIFo6OnZhbHVlT2YoMCl9OwoJCQkJbmV3X2luZm8uYW5zID0gaW5mb3NbZ11bZW5kb2Znb29kIC0gMV0uYW5zICsgMTsKCQkJCWF1dG8gc3RhcnRfb2Zfc2FtZV9hbnN3ZXIgPSBzdGQ6OnBhcnRpdGlvbl9wb2ludChpbmZvc1tnXS5iZWdpbigpLCBpbmZvc1tnXS5lbmQoKSwgWyZdKEluZm8gaW5mbykgewoJCQkJCXJldHVybiBpbmZvLmFucyA8IG5ld19pbmZvLmFucyAtIDE7CgkJCQl9KSAtIGluZm9zW2ddLmJlZ2luKCk7CgkJCQlhdXRvIGNlbnRlciA9IHN0ZDo6cGFydGl0aW9uX3BvaW50KGluZm9zW2ddLmJlZ2luKCksIGluZm9zW2ddLmVuZCgpLCBbJl0oSW5mbyBpbmZvKSB7CgkJCQkJcmV0dXJuIGluZm8ucG9zIDwgZ2Nkc1tqIC0gMV0uc2Vjb25kOwoJCQkJfSkgLSBpbmZvc1tnXS5iZWdpbigpOwoKCQkJCWlmIChjZW50ZXIgPj0gc3RhcnRfb2Zfc2FtZV9hbnN3ZXIpIHsKCQkJCQluZXdfaW5mby5jICs9IChwcmVmc1tnXVtjZW50ZXJdLnN1bSAtIHByZWZzW2ddW3N0YXJ0X29mX3NhbWVfYW5zd2VyXS5zdW0pICogKGdjZHNbal0uc2Vjb25kIC0gZ2Nkc1tqIC0gMV0uc2Vjb25kKTsKCQkJCX0KCQkJCWludCBzdCA9IChpbnQpIG1heChjZW50ZXIsIHN0YXJ0X29mX3NhbWVfYW5zd2VyKTsKCQkJCW5ld19pbmZvLmMgKz0gZ2Nkc1tqXS5zZWNvbmQgKiAocHJlZnNbZ11bZW5kb2Znb29kXS5zdW0gLSBwcmVmc1tnXVtzdF0uc3VtKSAtKHByZWZzW2ddW2VuZG9mZ29vZF0uc3VtY3BvcyAtIHByZWZzW2ddW3N0XS5zdW1jcG9zKTsKCQkJCWluZm9zW2ddLnB1c2hfYmFjayhuZXdfaW5mbyk7CgkJCQlwcmVmc1tnXS5wdXNoX2JhY2soe3ByZWZzW2ddLmJhY2soKS5zdW0gKyBuZXdfaW5mby5jLCBwcmVmc1tnXS5iYWNrKCkuc3VtY3BvcyArIG5ld19pbmZvLmMgKiBuZXdfaW5mby5wb3N9KTsKCQkJfQoJCX0KCgkJaW50IG1heGFucyA9IDA7CgkJZm9yIChpbnQgaTogcmFuZ2UobXgpKSB7CgkJCWlmICghaW5mb3NbaV0uZW1wdHkoKSkgewoJCQkJbWF4YW5zID0gbWF4KG1heGFucywgaW5mb3NbaV0uYmFjaygpLmFucyk7CgkJCX0KCQl9CgoJCVogcmVzOwoJCWZvciAoaW50IGk6IHJhbmdlKG14KSkgewoJCQlmb3IgKGF1dG8gdDogaW5mb3NbaV0pIHsKCQkJCWlmICh0LmFucyA9PSBtYXhhbnMpIHsKCQkJCQlyZXMgKz0gdC5jOwoJCQkJfQoJCQl9CgkJfQoKCQlvdXQgPDwgbWF4YW5zIDw8ICcgJyA8PCByZXMgPDwgIlxuIjsKCX0=
compilation info
prog.cpp:1:17: error: variable or field 'solve' declared void
void solve(std::istream& in, std::ostream& out) {
^
prog.cpp:1:12: error: 'istream' is not a member of 'std'
void solve(std::istream& in, std::ostream& out) {
^
prog.cpp:1:26: error: 'in' was not declared in this scope
void solve(std::istream& in, std::ostream& out) {
^
prog.cpp:1:30: error: 'ostream' is not a member of 'std'
void solve(std::istream& in, std::ostream& out) {
^
prog.cpp:1:44: error: 'out' was not declared in this scope
void solve(std::istream& in, std::ostream& out) {
^
stdout