سلام دوستان . من تصمیم گرفتم که از امروز , هر وقت به یه سوال جالب عملی برخورد کردم , اینجا هم سوال رو بذارم که اگر خواستین روش فکر کنین . به عنوان اولین سوال : http://codeforces.com/contest/474/problem/F

اگر سوال خوب نبود شما به بزرگی خودتون ببخشین D:

سوال به فارسی : N مورچه داریم ( n <= 1e5 ) مورچه ی i ام , قدرتی به اندازه ی s i داره ( قدرت هر مورچه کوچک تر مساوی با 1e9 هست) حالا q تا query داریم ( حدکثر 1e5 تا ) , توی هر query , دو تا عدد l , r بهمون می دن و هر کدوم از مورچه هایی که توی این بازه هست( از نظر اندیس) با تمام مورچه های دیگه ی این بازه می جنگه ( طبیعتا l <= r ) حالا اتفاقی که می افته اینه که وقتی دو تا مورچه با هم می جنگن , اگر قدرت اولی f باشه و قدرت دومی s باشه , اگر s بر f بخش پذیر باشه , امتیاز مورچه ی اول یه دونه افزایش پیدا می کنه و همچنین اگر f بر s بخش پذیر باشه امتیاز مورچه ی دوم یه دونه افزایش پیدا می کنه بعد از اینکه کل جنگ ها ی یه query اتفاق بیفته , عددی که ما باید برگردونیم تعداد کل مورچه های این بازه منهای مورچه هایی هست که توی همه ی جنگ ها ی مربوط به این کوئری امتیاز گرفتن ( یعنی اگر ۵ تا مورچه داشته باشیم و ۲ تا از مورچه ها ۴ امتیاز گرفته باشن , باید ۳ رو برگردونیم مثلا)

ترتیب ورودی :

n ( تعداد مورچه ها)

بعدش n تا عدد داریم که عدد i ام نشون دهنده ی قدرت مورچه ی i ام هست

بعدش q ( توی متن اصلی سوال t هست البته )

توی هر کدوم از q خط بعدی دو تا عدد l , r بهمون می دن که ما باید به همین ترتیب ورودی , جواب برای هر query رو برگردونیم

( من یکم متن سوال رو تغییر دادم ! D: )

مثال : ورودی :

5

2 4 2 3 1

4

5 1

5 2

5 3

5 4

خروجی :

4

4

1

1

توضیح : توی اولین کوئری , فقط مورچه ی اولی توی همه ی جنگ هاش امتیاز می گیره و جواب می شه کل مورچه ها منهای ۱ که می شه ۴

توی دومین کوئری , هیچ مورچه ای همه ی امتیاز ها رو نمی گیره و جواب می شه کل مورچه های این بازه

توی سومین کوئری , مورچه ی سوم و مورچه ی پنجم توی همه ی جنگ هاشون امتیاز می گیرن پس جواب می شه ۳ منهای ۲ که همون ۱ هست

توی آخرین کوئری هم , مورچه ی آخر توی همه ی جنگ هاش برنده می شه و جواب می شه ۲ منهای ۱ که همون ۱ هست

موفق باشین ( اگر کسی خواست بگه که فردا کد سوال رو بذارم) اگر حس کردین مشکلی توی متن فارسی هست بگین تا اصلاح بشه