#include <stdio.h>
#define maxn 100000
int gcd(int x,int y){// semmi trükk
if(y==0)return x;
return gcd(y,x%y);
}
// Mindig az elejéről vagy a végéről kapcsolunk le vagont, ezért minden
// mozgatás után egymásutáni vagonok vannak a pályán: a[i],a[i+1],..,a[j]
// A megoldás nyilván gcd(a[i],a[i+1],..,a[j]), ahol i-edik az első,
// j-edik az utolsó vagon ami a pályán van. Illetve 0 a válasz, ha üres a vonat.
// Legyen őrszem egy index i és j között, ha minden
// t<orszem-re bal[t]=gcd(a[t],..,a[orszem-1]) és
// u>=orszem-re jobb[u]=gcd(a[orszem],..,a[u]) ismert, akkor
// gcd(a[i],...,a[j])=gcd(bal[i],jobb[j])
// Azaz némi számolás után csak egyetlen gcd-t számolunk ki. De!
// Ha az őrszemet lekpcsolnánk akkor egy új őrszemet választunk:
// őrszem=(vonat_eleje+vonat_vege)/2.
// És pont ezt az algoritmust fogja a kód használni.
// Futásidőről:
// Az algoritmus (legfeljebb) 3*N darab lnko-t számít ki, bizonyítás:
// - Ha nincs új őrszem választása, akkor (legfeljebb) 2 lnko számítása kell,
// sőt, ha nem vagont kapcsolnak le, akkor (legfeljebb) 1 lnko-t számítunk
// - Ha új őrszem kell, akkor L hosszú vagonnál L darab lnko-t számítunk ki
// a bal[] és jobb[] tömb felépítéséhez, DE a kővetkező őrszem kiválasztásáig
// (vagy amíg el nem érjük az N mozgatást) (L-1)/2 olyan lépés is lesz a
// későbbiekben, amikor lekapcsolnak egy vagont, és akkor csak (legfeljebb)
// 1 darab lnko-t számítunk ki. Így ezen L/2 lépésre, ha szétosztjuk az extra
// L darab lnko-t, akkor minden lépésben legfeljebb 3 darab lnko-t számítunk ki.
// Mivel ez akkor is igaz, amikor nincs új őrszem választása, ezért N mozgatás
// esetén így (legfeljebb) 3*N darab lnko-t kell kiszámítanunk.
int main(void){
int i,j,n,bal[maxn],jobb[maxn],a[maxn];
int mozgatas,megoldas;
int orszem=0;
int vonat_eleje=0;
int vonat_vege=-1;
int vonat_hossz;
for(i=0;i<n;i++){
if(mozgatas==0){
vonat_vege++;
scanf("%d",&a
[vonat_vege
]); if(orszem<vonat_vege)jobb[vonat_vege]=gcd(jobb[vonat_vege-1],a[vonat_vege]);
else jobb[vonat_vege]=a[vonat_vege];
// bal[]-hoz tartozó vonatok: a(eleje)..a(orszem-1)
// jobb[]-hoz tartozó vonatok: a(orszem)..a(vege)
}
else if(mozgatas==1)vonat_vege--;// utolso vagon lekapcsolasa
else vonat_eleje++;// elso vagon lekapcsolasa
if(vonat_eleje>=orszem||orszem>vonat_vege){// uj orszem kell!!!!!
orszem=(vonat_eleje+vonat_vege)/2;// a kozepso vagon lesz az orszem
if(orszem>0){
bal[orszem-1]=a[orszem-1];
for(j=orszem-2;j>=vonat_eleje;j--)bal[j]=gcd(a[j],bal[j+1]);
}
jobb[orszem]=a[orszem];
for(j=orszem+1;j<=vonat_vege;j++)jobb[j]=gcd(a[j],jobb[j-1]);
}
vonat_hossz=vonat_vege-vonat_eleje+1;// vonat hossza
// a megoldas kiszamolasa, trivi esetek ellenorzese eloszor
if(vonat_hossz==0)megoldas=0;// ures vonat, ekkor 0 a valasz
else if(vonat_hossz==1)megoldas=a[vonat_vege];// 1 vagon van
else if(vonat_eleje<orszem)megoldas=gcd(bal[vonat_eleje],jobb[vonat_vege]);// altalanos eset
else megoldas=jobb[vonat_vege];// orszemtol balra nincs vagon
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIG1heG4gMTAwMDAwCgppbnQgZ2NkKGludCB4LGludCB5KXsvLyBzZW1taSB0csO8a2sKICAgIGlmKHk9PTApcmV0dXJuIHg7CiAgICByZXR1cm4gZ2NkKHkseCV5KTsKfQoKLy8gTWluZGlnIGF6IGVsZWrDqXLFkWwgdmFneSBhIHbDqWfDqXLFkWwga2FwY3NvbHVuayBsZSB2YWdvbnQsIGV6w6lydCBtaW5kZW4KLy8gbW96Z2F0w6FzIHV0w6FuIGVneW3DoXN1dMOhbmkgdmFnb25vayB2YW5uYWsgYSBww6FsecOhbjogYVtpXSxhW2krMV0sLi4sYVtqXQovLyBBIG1lZ29sZMOhcyBueWlsdsOhbiBnY2QoYVtpXSxhW2krMV0sLi4sYVtqXSksIGFob2wgaS1lZGlrIGF6IGVsc8WRLAovLyBqLWVkaWsgYXogdXRvbHPDsyB2YWdvbiBhbWkgYSBww6FsecOhbiB2YW4uIElsbGV0dmUgMCBhIHbDoWxhc3osIGhhIMO8cmVzIGEgdm9uYXQuCgovLyBMZWd5ZW4gxZFyc3plbSBlZ3kgaW5kZXggaSDDqXMgaiBrw7Z6w7Z0dCwgaGEgbWluZGVuCi8vIHQ8b3JzemVtLXJlICBiYWxbdF09Z2NkKGFbdF0sLi4sYVtvcnN6ZW0tMV0pIMOpcwovLyB1Pj1vcnN6ZW0tcmUgam9iYlt1XT1nY2QoYVtvcnN6ZW1dLC4uLGFbdV0pIGlzbWVydCwgYWtrb3IKLy8gZ2NkKGFbaV0sLi4uLGFbal0pPWdjZChiYWxbaV0sam9iYltqXSkKLy8gQXpheiBuw6ltaSBzesOhbW9sw6FzIHV0w6FuIGNzYWsgZWd5ZXRsZW4gZ2NkLXQgc3rDoW1vbHVuayBraS4gRGUhCi8vIEhhIGF6IMWRcnN6ZW1ldCBsZWtwY3NvbG7DoW5rIGFra29yIGVneSDDumogxZFyc3plbWV0IHbDoWxhc3p0dW5rOgovLyDFkXJzemVtPSh2b25hdF9lbGVqZSt2b25hdF92ZWdlKS8yLgovLyDDiXMgcG9udCBlenQgYXogYWxnb3JpdG11c3QgZm9namEgYSBrw7NkIGhhc3puw6FsbmkuCgovLyBGdXTDoXNpZMWRcsWRbDoKLy8gQXogYWxnb3JpdG11cyAobGVnZmVsamViYikgMypOIGRhcmFiIGxua28tdCBzesOhbcOtdCBraSwgYml6b255w610w6FzOgovLyAtIEhhIG5pbmNzIMO6aiDFkXJzemVtIHbDoWxhc3p0w6FzYSwgYWtrb3IgKGxlZ2ZlbGplYmIpIDIgbG5rbyBzesOhbcOtdMOhc2Ega2VsbCwKLy8gICBzxZF0LCBoYSBuZW0gdmFnb250IGthcGNzb2xuYWsgbGUsIGFra29yIChsZWdmZWxqZWJiKSAxIGxua28tdCBzesOhbcOtdHVuawovLyAtIEhhIMO6aiDFkXJzemVtIGtlbGwsIGFra29yIEwgaG9zc3rDuiB2YWdvbm7DoWwgTCBkYXJhYiBsbmtvLXQgc3rDoW3DrXR1bmsga2kKLy8gICBhIGJhbFtdIMOpcyBqb2JiW10gdMO2bWIgZmVsw6lww610w6lzw6loZXosIERFIGEga8WRdmV0a2V6xZEgxZFyc3plbSBraXbDoWxhc3p0w6Fzw6FpZwovLyAgICh2YWd5IGFtw61nIGVsIG5lbSDDqXJqw7xrIGF6IE4gbW96Z2F0w6FzdCkgKEwtMSkvMiBvbHlhbiBsw6lww6lzIGlzIGxlc3ogYSAKLy8gICBrw6lzxZFiYmlla2JlbiwgYW1pa29yIGxla2FwY3NvbG5hayBlZ3kgdmFnb250LCDDqXMgYWtrb3IgY3NhayAobGVnZmVsamViYikKLy8gICAxIGRhcmFiIGxua28tdCBzesOhbcOtdHVuayBraS4gw41neSBlemVuIEwvMiBsw6lww6lzcmUsIGhhIHN6w6l0b3N6dGp1ayBheiBleHRyYQovLyAgIEwgZGFyYWIgbG5rby10LCBha2tvciBtaW5kZW4gbMOpcMOpc2JlbiBsZWdmZWxqZWJiIDMgZGFyYWIgbG5rby10IHN6w6Ftw610dW5rIGtpLgovLyBNaXZlbCBleiBha2tvciBpcyBpZ2F6LCBhbWlrb3IgbmluY3Mgw7pqIMWRcnN6ZW0gdsOhbGFzenTDoXNhLCBlesOpcnQgTiBtb3pnYXTDoXMKLy8gZXNldMOpbiDDrWd5IChsZWdmZWxqZWJiKSAzKk4gZGFyYWIgbG5rby10IGtlbGwga2lzesOhbcOtdGFudW5rLgoKCmludCBtYWluKHZvaWQpewogIAogICAgaW50IGksaixuLGJhbFttYXhuXSxqb2JiW21heG5dLGFbbWF4bl07CiAgICBpbnQgbW96Z2F0YXMsbWVnb2xkYXM7CiAgICBpbnQgb3JzemVtPTA7CiAgICBpbnQgdm9uYXRfZWxlamU9MDsKICAgIGludCB2b25hdF92ZWdlPS0xOwogICAgaW50IHZvbmF0X2hvc3N6OwogICAgCiAgICBzY2FuZigiJWQiLCZuKTsKICAgIGZvcihpPTA7aTxuO2krKyl7CiAgICAgICAgc2NhbmYoIiVkIiwmbW96Z2F0YXMpOwoJaWYobW96Z2F0YXM9PTApewoJICAgdm9uYXRfdmVnZSsrOwoJICAgc2NhbmYoIiVkIiwmYVt2b25hdF92ZWdlXSk7CgkgICBpZihvcnN6ZW08dm9uYXRfdmVnZSlqb2JiW3ZvbmF0X3ZlZ2VdPWdjZChqb2JiW3ZvbmF0X3ZlZ2UtMV0sYVt2b25hdF92ZWdlXSk7CgkgICBlbHNlICAgICAgICAgICAgICAgICBqb2JiW3ZvbmF0X3ZlZ2VdPWFbdm9uYXRfdmVnZV07CgkgICAvLyBiYWxbXS1ob3ogdGFydG96w7Mgdm9uYXRvazogYShlbGVqZSkuLmEob3JzemVtLTEpCgkgICAvLyBqb2JiW10taG96IHRhcnRvesOzIHZvbmF0b2s6IGEob3JzemVtKS4uYSh2ZWdlKQoJfQoJZWxzZSBpZihtb3pnYXRhcz09MSl2b25hdF92ZWdlLS07Ly8gdXRvbHNvIHZhZ29uIGxla2FwY3NvbGFzYQoJZWxzZSB2b25hdF9lbGVqZSsrOy8vIGVsc28gdmFnb24gbGVrYXBjc29sYXNhCgkKCWlmKHZvbmF0X2VsZWplPj1vcnN6ZW18fG9yc3plbT52b25hdF92ZWdlKXsvLyB1aiBvcnN6ZW0ga2VsbCEhISEhCgkgICBvcnN6ZW09KHZvbmF0X2VsZWplK3ZvbmF0X3ZlZ2UpLzI7Ly8gYSBrb3plcHNvIHZhZ29uIGxlc3ogYXogb3JzemVtCgkgICBpZihvcnN6ZW0+MCl7CgkgICAgICBiYWxbb3JzemVtLTFdPWFbb3JzemVtLTFdOwoJICAgICAgZm9yKGo9b3JzemVtLTI7aj49dm9uYXRfZWxlamU7ai0tKWJhbFtqXT1nY2QoYVtqXSxiYWxbaisxXSk7CgkgICB9CgkgICBqb2JiW29yc3plbV09YVtvcnN6ZW1dOwoJICAgZm9yKGo9b3JzemVtKzE7ajw9dm9uYXRfdmVnZTtqKyspam9iYltqXT1nY2QoYVtqXSxqb2JiW2otMV0pOwoJfQoJCgl2b25hdF9ob3Nzej12b25hdF92ZWdlLXZvbmF0X2VsZWplKzE7Ly8gdm9uYXQgaG9zc3phCgkKCS8vIGEgbWVnb2xkYXMga2lzemFtb2xhc2EsIHRyaXZpIGVzZXRlayBlbGxlbm9yemVzZSBlbG9zem9yCiAgICAgICAgaWYodm9uYXRfaG9zc3o9PTApbWVnb2xkYXM9MDsvLyB1cmVzIHZvbmF0LCBla2tvciAwIGEgdmFsYXN6CgllbHNlIGlmKHZvbmF0X2hvc3N6PT0xKW1lZ29sZGFzPWFbdm9uYXRfdmVnZV07Ly8gMSB2YWdvbiB2YW4KCWVsc2UgaWYodm9uYXRfZWxlamU8b3JzemVtKW1lZ29sZGFzPWdjZChiYWxbdm9uYXRfZWxlamVdLGpvYmJbdm9uYXRfdmVnZV0pOy8vIGFsdGFsYW5vcyBlc2V0CgllbHNlIG1lZ29sZGFzPWpvYmJbdm9uYXRfdmVnZV07Ly8gb3JzemVtdG9sIGJhbHJhIG5pbmNzIHZhZ29uCglwcmludGYoIiVkXG4iLG1lZ29sZGFzKTsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==