Մրցույթ
Ռոբերտը և Դավիթը պատրաստել են
n հատ խնդիր, որոնց որոշ մասը պետք է օգտագործվի R&D կոչվող մրցույթում։ Խնդիրները համարակալված են 1-ից n թվերով։ Ամեն խնդիր լուծվում է որոշակի ալգորիթմի միջոցով․ i-րդ խնդիրը լուծվում է ai համարի ալգորիթմով (ալգորիթմները նույնպես համարակալված են)։ Մրցույթում օգտագործվող խնդիրների վերջնական ընտրությունը կայացնում է R&D մրցույթի տնօրեն Ալեքսանդրը, ում կազմված խնդիրներից ոչ մեկը դուր չի գալիս։q օրերի ընթացքում տեղի են ունենում երկու տեսակի իրադարձություններ․1 l r y. Ռոբերտը և Դավիթը փոխարինում են l-ից r համարներով խնդիրները y ալգորիթմով լուծվող խնդիրներով։ Ֆորմալ ai:=y:2 l r. Ռոբերտը և Դավիթը Ալեքսանդրին են ներկայացնում l-ից r համարներով խնդիրները, իսկ Ալեքսանդրը ընտրում է [l,r] հատվածի [l1,r1] ենթահատված (l ≤ l1 ≤ r1 ≤ r), որը պարունակում է մինիմալ քանակությամբ խնդիրներ, բայց պարունակում է [l,r] հատվածում առկա ալգորիթմներից յուրաքանչյուրով լուծվող գոնե մեկ խնդիր։ Ֆորմալ գոյություն չունի այնպիսի i, որ l ≤ i ≤ r և ai ≠ aj կամայական j-ի համար, որտեղ l1 ≤ j ≤ r1:Յուրաքանչյուր
2-րդ տեսակի հարցման համար անհրաժեշտ է արտածել Ալեքսանդրի ընտրած ենթահատվածի երկարությունը։Մուտքային տվյալներ
Առաջին տողում տրված է մեկ բնական թիվ
n(1 ≤ n ≤ 100000)։ Հաջորդ տողում տրված են n թվեր․ a հաջորդականություն (ai ≤ 10)։ Հաջորդ տողում տրված է q(1 ≤ q ≤ 100000) թիվը: Հաջորդ q տողերից յուրաքանչուրում տրված է հերթական հարցման նկարագրությունը․ 1 l r y, կամ 2 l r տեսքի (1 ≤ l ≤ r ≤ n y ≤ 10)։Ելքային տվյալներ
Յուրաքանչյուր
2-րդ տեսակի հարցման համար անհրաժեշտ է արտածել Ալեքսանդրի ընտրած ենթահատվածի երկարությունը։Օրինակներ
Մուտք | Ելք |
3
1 2 3
3
2 1 3
1 1 3 1
2 1 3 | 3
1 |
Մուտք | Ելք |
10
2 3 4 1 2 3 4 2 3 2
10
2 2 10
1 2 5 1
2 3 7
2 1 10
1 4 6 3
2 4 7
2 1 10
2 3 7
2 7 10
2 2 9 | 4 3 4 2 6 5 3 6 |
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները,
- Ենթախնդիր 1 (10 միավոր)
n, q ≤ 100
- Ենթախնդիր 2 (11 միավոր)
n, q ≤ 4000
- Ենթախնդիր 3 (12 միավոր)
ai, y ≤ 2
- Ենթախնդիր 4 (22 միավոր)
1ին տեսակի հարցումներ չկան,
- Ենթախնդիր 5 (15 միավոր)
1ին տեսակի հարցումներումl = r
- Ենթախնդիր 6 (17 միավոր)
ai, y ≤ 5
- Ենթախնդիր 7 (13 միավոր) լրացուցիչ սահմանափակումներ չկան
Constraints
Time limit: 30 seconds
Memory limit: 512 MB
Output limit: 1 MB