Problem:
 Score : 1200 points    Problem Statement Takahashi is an expert of Clone Jutsu, a secret art that creates copies of his body.  On a number line, there are N copies of Takahashi, numbered 1 through N .
The i -th copy is located at position X_i and starts walking with velocity V_i in the positive direction at time 0 .  Kenus is a master of Transformation Jutsu, and not only can he change into a person other than himself, but he can also transform another person into someone else.  Kenus can select some of the copies of Takahashi at time 0 , and transform them into copies of Aoki, another Ninja.
The walking velocity of a copy does not change when it transforms.
From then on, whenever a copy of Takahashi and a copy of Aoki are at the same coordinate, that copy of Takahashi transforms into a copy of Aoki.  Among the 2^N ways to transform some copies of Takahashi into copies of Aoki at time 0 , in how many ways will all the copies of Takahashi become copies of Aoki after a sufficiently long time?
Find the count modulo 10^9+7 .      Constraints  1 ≤ N ≤ 200000  1 ≤ X_i,V_i ≤ 10^9(1 ≤ i ≤ N)  X_i and V_i are integers.  All X_i are distinct.  All V_i are distinct.         Input The input is given from Standard Input in the following format:  N  X_1  V_1 : X_N  V_N       Output Print the number of the ways that cause all the copies of Takahashi to turn into copies of Aoki after a sufficiently long time, modulo 10^9+7 .        Sample Input 1 3
2 5
6 1
3 7      Sample Output 1 6  All copies of Takahashi will turn into copies of Aoki after a sufficiently long time if Kenus transforms one of the following sets of copies of Takahashi into copies of Aoki: (2) , (3) , (1,2) , (1,3) , (2,3) and (1,2,3) .       Sample Input 2 4
3 7
2 9
8 16
10 8      Sample Output 2 9

Solution (Python):
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10**9+7
inv=pow(2,mod-2,mod)

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))


M=len(const)
const=[(-10**15,0)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    l,r=const[id]
    l=max(l,Rconst[id-1]+1)
    res+=dp[id-1]*(pow(2,r-L+1,mod)-1)*pow(2,L-l,mod)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1
ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
import fileinput


MODULO = 1000000007
n = 0



def handle_input():
    iterator = fileinput.input()
    global n
    n = int(next(iterator))
    takahashis = [None] * n
    for i in xrange(n):
        x, v = next(iterator).split()
        takahashis[i] = (int(x), int(v))
    return takahashis


def build_blocks(takahashis):
    result = [-1] * (n + 1)
    max_velocities = [0] * n
    min_velocities = [MODULO] * (n + 1)
    for i in xrange(n):
        max_velocities[i] = max(max_velocities[i - 1], takahashis[i][1])
    for i in xrange(n-1, -1, -1):
        min_velocities[i] = min(min_velocities[i + 1], takahashis[i][1])
    for i in xrange(n):
        current_velocity = takahashis[i][1]
        block_start = bisect_left(max_velocities, current_velocity)
        block_end = bisect_right(min_velocities, current_velocity) - 1
        result[block_end] = max(result[block_end], block_start)
    return result


def compute_possibilities(blocks):
    possibilities = [1] * (n + 2)
    zeros_end_cursor = -2
    for current_position in xrange(n):
        result = 2 * possibilities[current_position - 1]
        
        while zeros_end_cursor < blocks[current_position] - 1:
            result -= possibilities[zeros_end_cursor]
            zeros_end_cursor += 1
        possibilities[current_position] = result % MODULO
    return possibilities[n - 1]


def main():
    takahashis = handle_input()
    takahashis.sort()
    blocks = build_blocks(takahashis)
    return compute_possibilities(blocks)


if __name__ == '__main__':
    print main()