მედიანის მაღლა

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2011/12, NOV, GOLD


ფერმერ ჯონმა ერთ ხაზში ჩაამწკრივა N (1 <= N <= 100,000) ძროხა,რათა გაეზომა მათი სიმაღლეები. i-ური ძროხის სიმაღლეა H_i (1 <= H_i <= 1,000,000,000) ნანომეტრებში - ჯონს უყვარს სიზუსტე. მას სურს მომიჯნე ძროხების სხვადასხვა ჯგუფების სურათზე გადაღება და ამ სურათების გამოფენაზე გაგზავნა. გამოფენაზე მიღებულია უცნაური წესი: იქ სურათი მიიღება, თუ მასზე აღბეჭდილია ის ძროხების ჯგუფი, რომლის მედიანის სიმაღლე არ არის ნაკლები ვიდრე წინასწარ განსაზღვრული რიცხვი X (1 < = X < = 1,000,000,000). განვსაზღვროთ A[1...K] მასის მედიანა როგორც A[ceiling(K/2)] A მასივის დალაგების შემდეგ, სადაც ceiling(K/2) არის K/2-ის დამრგვალება უახლოეს მთელისკენ. მაგალითად {7, 3, 2, 6} სიმრავლი მედიანა არის 6, ხოლო {5,4, 8} - არის 5. დათვალეთ ყველა იმ უწყვეტი ჯგუფის რაოდენობა, რომელთა სურათები მიიღება გამოფენაზე.

შემავალი მონაცემების ფორმატი: * სტრიქონი 1: ორი მთელი N და X. * სტრიქონები 2..N+1: სტრიქონი i+1 მოიცავს ერთ მთელ H_i რიცხვს. გამომავალი მონაცემების ფორმატი: * სტრიქონი 1: ერთი მთელი - იმ ჯგუფების რაოდენობა, რომელთა მედიანა მეტია ან ტოლია X-ზე. შესაძლოა, პასუხი ვერ დაეტიოს 32 ბიტიან რიცხვში.




მაგალითები

შესატანი მონაცემები
4 6 10 5 6 2 დაკოპირება
გამოსატანი მონაცემები
7 დაკოპირება

შენიშვნა

ჯონის 4 ძროხის სიმაღლეებია 10, 5, 6, 2. ყველა უწყვეტი 10 ჯგუფიდან არსებობს 7, რომელთა მედიანა მეტია ან ტოლია 6-ზე: {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10,5, 6}, {10, 5, 6, 2}.