Արևելյան պողոտայի մայթը
Արևելյան պողոտան ձգվում է արևմուտքից արևելք հազարավոր մետրեր։ Մեզ հետաքրքրում է միայն պողոտայի մի մայթը, որի երկարությամբ կան բազմաթիվ խանութներ, յուրաքանչյուրին մեկ միավոր երկարությամբ մայթ է բաժին հասնում։ Յուրաքանչյուր խանութի տնօրեն իր պարտքն է համարում իր խանութի առաջը գեղեցկացնել և սալիկապատել մայթի հատվածը։ Արդյունքում մայթի տարբեր հատվածներ ծածկված են տարբեր տեսքի սալիկներով։ Բացի այդ ժամանակ առ ժամանակ որևէ խանութի սեփականատեր որոշում է նորոգել տարածքը և փոխել իր հատվածի սալիկները։
Յուրաքանչյուր նորոգումից հետո հարկավոր է պարզել, թե քանի նույնատիպ անընդհատ կտորներից է բաղկացած մայթը։
Մուտքային տվյալներ
Առաջին տողում տրված է Արևելյան պողոտայի մայթի
n երկարությունը։ Հաջորդ տողը պարունակում է n ամբողջ թվեր, որոնք նկարագրում են մայթի հատվածների սալիկների տիպերը։ Այդ թվերը կարող են լինել նաև բացասական և բացարձակ արժեքով չեն գերազանցում q տողերից յուրաքանչյուրը պարունակում է տվյալներ հերթական նորոգման վերաբերյալ։ Այն բաղկացած է թվազույգից՝ առաջին թիվը ցույց է տալիս նորոգվող հատվածի h համարը (1 ≤ h ≤ n), երկրորդ թիվը ցույց է տալիս նոր սալիկների տիպը։Ելքային տվյալներ
Ելքում պետք է արտածել
q տող։ i-րդ տողում պետք է արտածել i-րդ նորոգումից հետո մայթի նույնատիպ անընդհատ կտորների քանակը։Օրինակ
Մուտք | Ելք |
6
1 1 1 1 1 1
4
3 2
5 2
4 2
5 1 | 3
5
3
3 |
Օրինակի պարզաբանումը։
Սկզբում մայթի բոլոր հատվածները նույնատիպ են՝ 111111։ Առաջին նորոգումից հետո այն ստանում է այսպիսի տեսք՝ 112111 և բաղկացած է 3 նույնատիպ կտորներից։ Երկրորդը նորոգվում է 5-րդ հատվածը և ստացվում է՝ 112121։ Այժմ նույնատիպ անընդհատ կտորների քանակը 4 է։ Ապա 4-րդ հատվածը դառնում է 2 (112221) և պատասխանը կրկին դառնում է 3։ Վերջում 5-րդ հատվածը կրկին դառնում է 1, բայց դրանից պատասխանը չի փոխվում։
Աղբյուրը. Հանրապետական 2019
Constraints
Time limit: 1.6 seconds
Memory limit: 512 MB
Output limit: 5 MB